We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to solve the PSPACE-complete problem QUANTIFIED 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules, are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential time and polynomial space problems that cannot be solved in polynomial time, unless P = PSPACE.
Porreca, A., Leporati, A., Mauri, G., Zandron, C. (2011). P systems with active membranes: Trading time for space. NATURAL COMPUTING, 10(1), 167-182 [10.1007/s11047-010-9189-x].
P systems with active membranes: Trading time for space
PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2011
Abstract
We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to solve the PSPACE-complete problem QUANTIFIED 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules, are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential time and polynomial space problems that cannot be solved in polynomial time, unless P = PSPACE.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
