P System - As A Computational Model

As A Computational Model

Most P systems variants are computationally universal. This extends even to include variants that do not use rule priorities, usually a fundamental aspect of P systems.

As a model for computation, P systems offer the attractive possibility of solving NP-complete problems in less-than exponential time. Some P system variants are known to be capable of solving the SAT (boolean satisfiability) problem in linear time and, owing to all NP-complete problems being equivalent, this capability then applies all such problems. As there is no current method of directly implementing a P system in its own right, their functionality is instead emulated, solving NP-complete problems in linear time remains theoretical. However, it has also been proven that any deterministic P system may be simulated on a Turing Machine in polynomial time.