In this paper, we consider recognizer P systems with antimatter and the influence of the matter/antimatter annihilation rules having weak priority over all the other rules or not. We first provide a uniform family of P systems with active membranes which solves the strongly NP-complete problem SAT, the Satisfiability Problem, without polarizations and without dissolution, yet with division for elementary membranes and with matter/antimatter annihilation rules having weak priority over all the other rules. Then we show that without this weak priority of the matter/antimatter annihilation rules over all the other rules we only obtain the complexity class P.
Diaz Pernil, D., Alhazov, A., Freund, R., Gutierrez Naranjo, M., Leporati, A. (2015). Recognizer P systems with antimatter. ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 18(3), 201-217.
Recognizer P systems with antimatter
ALHAZOV, ARTIOMSecondo
;LEPORATI, ALBERTO OTTAVIOUltimo
2015
Abstract
In this paper, we consider recognizer P systems with antimatter and the influence of the matter/antimatter annihilation rules having weak priority over all the other rules or not. We first provide a uniform family of P systems with active membranes which solves the strongly NP-complete problem SAT, the Satisfiability Problem, without polarizations and without dissolution, yet with division for elementary membranes and with matter/antimatter annihilation rules having weak priority over all the other rules. Then we show that without this weak priority of the matter/antimatter annihilation rules over all the other rules we only obtain the complexity class P.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.