A variant of P-systems, recently introduced, considers membranes which can multiply by division. Two types of division are considered: division for elementary membranes (i.e. membranes not containing other membranes) and for non-elementary membranes. In two recent papers it is shown how to solve the Satisfiability problem and the Hamiltonian Path problem (two well-known NP-complete problems) in linear time with respect to the input length, using this variant of P systems. We show in this paper that P systems with division for elementary membranes only suffice to solve these two peoblems in linear time.What about the possibility of solving NP-complete problems in polynomial time using P systems without membrane division? We how, moreover, that (if P≠NP) Deterministic P systems without membrane division are not able to solve NP-complete problems in polynomial time.
Zandron, C., Ferretti, C., Mauri, G. (2001). Solving NP-complete problems using P systems with active membranes. In Unconventional Models of Computation - UMC'2K (pp.289-301). London : Springer.
Solving NP-complete problems using P systems with active membranes
ZANDRON, CLAUDIO;FERRETTI, CLAUDIO;MAURI, GIANCARLO
2001
Abstract
A variant of P-systems, recently introduced, considers membranes which can multiply by division. Two types of division are considered: division for elementary membranes (i.e. membranes not containing other membranes) and for non-elementary membranes. In two recent papers it is shown how to solve the Satisfiability problem and the Hamiltonian Path problem (two well-known NP-complete problems) in linear time with respect to the input length, using this variant of P systems. We show in this paper that P systems with division for elementary membranes only suffice to solve these two peoblems in linear time.What about the possibility of solving NP-complete problems in polynomial time using P systems without membrane division? We how, moreover, that (if P≠NP) Deterministic P systems without membrane division are not able to solve NP-complete problems in polynomial time.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
