Repositorio de producción científica de la Universidad de Sevilla

Decision P Systems and the P =NP Conjecture

 

Advanced Search
 
Opened Access Decision P Systems and the P =NP Conjecture
Cites

Show item statistics
Icon
Export to
Author: Pérez Jiménez, Mario de Jesús
Romero Jiménez, Álvaro
Sancho Caparrini, Fernando
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2003
Published in: Membrane Computing. Lecture Notes in Computer Science, vol.2597
ISBN/ISSN: 978-3-540-00611-4
0302-9743
Document type: Chapter of Book
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.
Size: 227.5Kb
Format: PDF

URI: http://hdl.handle.net/11441/47982

DOI: 10.1007/3-540-36490-0_27

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)