Decision P systems and the P≠NP conjecture

Abstract:

We introduce decision P systems, which are a class of P systems with symbol-objects and external output. The main result of the paper is the following: if there exists an NP-complete problem that cannot be solved in polynomial time, with respect to the input length, by a deterministic decision P system constructed in polynomial time, then P ≠ NP. From Zandron-Ferreti-Mauri's theorem it follows that if P ≠ NP, then no NP-complete problem can be solved in polynomial time, with respect to the input length, by a deterministic P system with active membranes but without membrane division, constructed in polynomial time from the input. Together, these results give a characterization of P ≠ NP in terms of deterministic P systems. © Springer-Verlag Berlin Heidelberg 2003.

Año de publicación:

2003

Keywords:

Fuente:

scopus