@article {547,
title = {Decision P systems and the P/=NP conjecture},
journal = {Lecture Notes in Computer Science},
volume = {2597},
year = {2003},
pages = {388-399},
publisher = {Springer},
address = {Amsterdam, The Netherlands},
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{\textquoteright}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. },
isbn = {978-3-540-00611-4},
issn = {0302-9743},
doi = {10.1007/3-540-36490-0_27},
url = {http://dx.doi.org/10.1007/3-540-36490-0_27},
author = {Mario J. P{\'e}rez-Jim{\'e}nez and {\'A}lvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}
}