Connections between Space-Bounded Molecular Computation and Classical Complexity Theory

由于其指数并行性，分子计算为解决传统计算机无法解决的重要问题提供了希望。各种分子操作被认为是可行的；由于不清楚哪些操作将有效地实现，因此使用最简单操作的算法是首选。特别是，进程之间的通信可能是不可能的。并行性和运行时间是需要有效利用的资源。已知具有有限运算集、多项式时间和指数并行性的分子计算机可以求解NP类中的任何问题。通过进一步限制并行性，得到了NP的各种有界不确定性子类。本项目研究分子计算类与这些NP子类之间的关系。虽然许多处理重要问题的分子算法使用2n并行性，但这严重限制了这些算法可以解决的问题的规模。在过去的二十年中，经典串行算法在求解3-SAT、图着色、独立集等重要np完全问题时的运行时间从2n提高到2cn。使用有界不确定性作为算法设计技术，本项目将开发更有效的分子算法来解决重要的np完全问题，如3-SAT、图着色和独立集。＊＊＊

With its exponential parallelism, molecular computing offers the hope of solving important problems that have resisted solution on conventional computers. Various molecular operations have been proposed as feasible; because it is unclear which operations will be usefully implementable, algorithms that use the simplest operations are to be preferred. In particular, communication between processes may be impossible. Parallelism and running time are resources to be exploited efficiently. It is known that molecular computers with limited operations sets, polynomial time, and exponential parallelism can solve any problem in the class NP. By further limiting the parallelism, various bounded-nondeterminism subclasses of NP are obtained. This project investigates the relationships among molecular computation classes and these NP subclasses. While many molecular algorithms for important problems use 2n parallelism, this severely limits the size of problems that those algorithms can solve. In the last two decades there has been an improvement from 2n to 2cn for various c1 in the running time of classical serial algorithms for important NP-complete problems like 3-SAT, graph coloring, and independent set. Using bounded nondeterminism as an algorithm design technique, this project will develop more efficient molecular algorithms for important NP-complete problems, such as 3-SAT, graph coloring, and independent set. ***