Enzymatic Numerical P Systems Using Elementary Arithmetic Operations

摘要

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.