Decision P systems and the P≠NP conjecture

TitleDecision P systems and the P≠NP conjecture
Publication TypeJournal Papers
Year of Publication2003
AuthorsPérez-Jiménez, M. J., Romero-Jiménez Á., & Sancho-Caparrini F.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-540-00611-4
Place PublishedAmsterdam, The Netherlands

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.

ISSN Number0302-9743