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.
slide + paper
Scientifica
PP-completeness; Membrane Computing; Satisfiability
English
Eleventh International Conference on Membrane Computing
978-3-642-18122-1
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].
Porreca, A; Leporati, A; Mauri, G; Zandron, C
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10281/32413
Citazioni
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 6
Social impact