Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximallly parallel way.

Zandron, C., Leporati, A., Ferretti, C., Mauri, G., Pérez Jiménez, M. (2008). On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. FUNDAMENTA INFORMATICAE, 87(1), 79-91.

On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution

ZANDRON, CLAUDIO;LEPORATI, ALBERTO OTTAVIO;FERRETTI, CLAUDIO;MAURI, GIANCARLO;
2008

Abstract

Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximallly parallel way.
Articolo in rivista - Articolo scientifico
P systems, active membranes, membrane division, membrane dissolution, NP completeness, 3-SAT
English
79
91
13
Zandron, C., Leporati, A., Ferretti, C., Mauri, G., Pérez Jiménez, M. (2008). On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. FUNDAMENTA INFORMATICAE, 87(1), 79-91.
Zandron, C; Leporati, A; Ferretti, C; Mauri, G; Pérez Jiménez, M
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/5305
Citazioni
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 19
Social impact