%0 Generic
%D 2003
%T Decision P systems and the P≠NP conjecture
%A Mario J. Pérez-Jiménez
%A Álvaro Romero-Jiménez
%A Fernando Sancho-Caparrini
%C Amsterdam, The Netherlands
%I Springer
%P 388-399
%R 10.1007/3-540-36490-0_27
%U http://dx.doi.org/10.1007/3-540-36490-0_27
%V 2597
%X 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.
%@ 978-3-540-00611-4