Molecular computing, bounded nondeterminism, and efficient recursion

The maximum number of strands used is an important measure of a molecular a lgorithm's complexity. This measure is also called the volume used by the a lgorithm. Every problem that can be solved by an NP Turing machine with b(n ) binary nondeterministic choices can be solved by molecular computation in a polynomial number of steps, with four test tubes, in volume 2(b(n)). We identify a large class of recursive algorithms that can be implemented usin g bounded nondeterminism. This yields improved molecular algorithms for imp ortant problems like 3-SAT, independent set, and 3-colorability.