P systems with active membranes have the ability of solving computationally hard problems. In this paper, the authors prove that uniform families of P systems with active membranes operating in polynomial time can solve the whole class of PP decision problems, without using nonelementary membrane division or dissolution rules. This result also holds for families having a stricter uniformity condition than the usual one.
Porreca, A., Leporati, A., Mauri, G., Zandron, C. (2011). Elementary Active Membranes Have the Power of Counting. INTERNATIONAL JOURNAL OF NATURAL COMPUTING RESEARCH, 2(3), 35-48 [10.4018/jncr.2011070104].
Elementary Active Membranes Have the Power of Counting
PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2011
Abstract
P systems with active membranes have the ability of solving computationally hard problems. In this paper, the authors prove that uniform families of P systems with active membranes operating in polynomial time can solve the whole class of PP decision problems, without using nonelementary membrane division or dissolution rules. This result also holds for families having a stricter uniformity condition than the usual one.
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.
