We prove that a uniform family of P systems with active membranes, where division rules only operate on elementary membranes and dissolution rules are avoided, can be used to solve the following PP-complete decision problem in polynomial time: given a Boolean formula of m variables in 3CNF, do at least √2m among the 2m possible truth assignments satisfy it? As a consequence, the inclusion PP⊆PMCAM(−d,−n) holds: this provides an improved lower bound on the class of languages decidable by this kind of P systems.
Porreca, A., Leporati, A., Mauri, G., Zandron, C. (2010). P Systems with Elementary Active Membranes: Beyond NP and coNP. In Membrane Computing. Proceedings of the 11th International Conference on Membrane Computing (CMC11) (pp.338-347). Berlin : Springer Verlag [10.1007/978-3-642-18123-8_26].
P Systems with Elementary Active Membranes: Beyond NP and coNP
PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2010
Abstract
We prove that a uniform family of P systems with active membranes, where division rules only operate on elementary membranes and dissolution rules are avoided, can be used to solve the following PP-complete decision problem in polynomial time: given a Boolean formula of m variables in 3CNF, do at least √2m among the 2m possible truth assignments satisfy it? As a consequence, the inclusion PP⊆PMCAM(−d,−n) holds: this provides an improved lower bound on the class of languages decidable by this kind of P systems.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
