Biomolecular realization of a parallel architecture for solving combinatorial problems

摘要

A coherent approach to the problem of carrying out com- putations in aqueous solution is provided. The conceptual level of the pre- sentation provides for many different molecular realizations to be explored in the future. Several possibilities are suggested. Our initial implementations have provided wet lab prototype computations for two of the classical N P complete graph theoretical problems: the maximum independent set problem and the minimum dominating set problem. A wet lab prototype computation is in progress for the determination of the satisfiability of sets of disjunctive clauses.