id: 05132985
dt: j
an: 05132985
au: Gutiérrez-Naranjo, Miguel A.; Pérez-Jiménez, Mario J.; Romero-Campero,
    Francisco J.
ti: A uniform solution to SAT using membrane creation.
so: Theor. Comput. Sci. 371, No. 1-2, 54-61 (2007).
py: 2007
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: natural computing; membrane computing; cellular complexity classes; SAT
    problem
ci: 
li: doi:10.1016/j.tcs.2006.10.013
ab: Summary: In living cells, new membranes are produced basically through two
    processes: mitosis and autopoiesis. These two processes have inspired
    two variants of cell-like membrane systems, namely P systems with
    active membranes and P systems with membrane creation. In this paper,
    we provide the first uniform, efficient solution to the SAT problem in
    the framework of recogniser P systems with membrane creation using
    dissolution rules. Recently the authors have proved that if the
    dissolution rules are not allowed to be used, then the polynomial
    complexity class associated with this variant of P systems is the
    standard complexity class P. This result, together with the main result
    of this paper, shows the surprising role of the apparently
    “innocent” operation of membrane dissolution. The use of this type
    of rule establishes the difference between efficiency and
    non-efficiency for P systems with membrane creation, and provides a
    barrier between P and NP (assuming P $\ne$ NP).
rv: