We prove that all-parallel enzymatic numerical P systems whose production functions can be expressed as a combination of sums, differences, products and integer divisions characterise PSPACE when working in polynomial time. We also show that, when only sums and differences are available, exactly the problems in P can be solved in polynomial time. These results are proved by showing how EN P systems and random access machines, running in polynomial time and using the same basic operations, can simulate each other efficiently.
Leporati, A., Mauri, G., Porreca, A., Zandron, C. (2014). Enzymatic Numerical P Systems Using Elementary Arithmetic Operations. In CMC 2013 – 14th International Conference on Membrane Computing, Revised Selected Papers (pp.249-264). Springer [10.1007/978-3-642-54239-8_18].
Enzymatic Numerical P Systems Using Elementary Arithmetic Operations
LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO;ZANDRON, CLAUDIO
2014
Abstract
We prove that all-parallel enzymatic numerical P systems whose production functions can be expressed as a combination of sums, differences, products and integer divisions characterise PSPACE when working in polynomial time. We also show that, when only sums and differences are available, exactly the problems in P can be solved in polynomial time. These results are proved by showing how EN P systems and random access machines, running in polynomial time and using the same basic operations, can simulate each other efficiently.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
