C. Zandron, C. Ferretti, G. Mauri
Solving NP-complete problems using P systems with active membranes.
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
inside) and division 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 problems in linear time.
What about the possibility of solving NP complete problems in polynomial
time using P systems without membrane division? We show, moreover,
that (if $P \neq NP$) Deterministic P Systems without membrane division
are not able to solve NP complete problems in polynomial time.