A general resolution of intractable problems in polynomial time through DNA Computing.
Based on a set of known biological operations, a general resolution of intractable problems in polynomial time through DNA Computing is presented. This scheme has been applied to solve two NP-Hard problems (Minimization of Open Stacks Problem and Matrix Bandwidth Minimization Problem) and three co-NP-Complete problems (associated with Hamiltonian Path, Traveling Salesman and Hamiltonian Circuit), which have not been solved with this model. Conclusions and open questions concerning the computational capacity of this model are presented, and research topics are suggested.
Instituto Tecnológico de Aeronáutica - CTA/ITA/IEC, Praça Mal. Eduardo Gomes, 50, São José dos Campos, SP 12228-900, Brazil. Electronic address: alonso@ita.br.
C A A
CA
Sanches
Instituto Tecnológico de Aeronáutica - CTA/ITA/IEC, Praça Mal. Eduardo Gomes, 50, São José dos Campos, SP 12228-900, Brazil. Electronic address: soma@ita.br.
N Y
NY
Soma
D000465:Algorithms; D000818:Animals; D039301:Computers, Molecular / Q000639:trends*; D003205:Computing Methodologies; D004247:DNA / Q000235:genetics; D006801:Humans; D015233:Models, Statistical
D004247:DNA
Co-NP class; DNA Computing; NP-Hard problems