We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class NP. © 2009 Elsevier B.V. All rights reserved.

Porreca, A., Mauri, G., Zandron, C. (2010). Non-confluence in divisionless P systems with active membranes. THEORETICAL COMPUTER SCIENCE, 411(6), 878-887 [10.1016/j.tcs.2009.07.032].

Non-confluence in divisionless P systems with active membranes

PORRECA, ANTONIO ENRICO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2010

Abstract

We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class NP. © 2009 Elsevier B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
Complexity theory; Membrane computing;
English
2010
411
6
878
887
none
Porreca, A., Mauri, G., Zandron, C. (2010). Non-confluence in divisionless P systems with active membranes. THEORETICAL COMPUTER SCIENCE, 411(6), 878-887 [10.1016/j.tcs.2009.07.032].
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: https://hdl.handle.net/10281/12014
Citazioni
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 14
Social impact