|Title||Decision P systems and the P≠NP conjecture|
|Publication Type||Journal Papers|
|Year of Publication||2003|
|Authors||Pérez-Jiménez, M. J., Romero-Jiménez Á., & Sancho-Caparrini F.|
|Journal Title||Lecture Notes in Computer Science|
|Publisher||Springer Berlin / Heidelberg|
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.