Authors: Bin Fu and Richard Beigel
Abstract: The number of molecular strands used by a molecular algorithm is an important measure of the algorithm's complexity. This measure is also called the space used by the algorithm. We prove that three important polynomial-time models of molecular computation with bounded space are equivalent to models of polynomial-time Turing machine computation with bounded nondeterminism. Without any assumption, we show that the Split operation does not increase the power of polynomial-time molecular computation. Assuming a plausible separation between Turing machine complexity classes, the Amplify operation does increase the power of polynomial-time molecular computation.