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.
Read more about this topic: P System
Famous quotes containing the word model:
“The striking point about our model family is not simply the compete-compete, consume-consume style of life it urges us to follow.... The striking point, in the face of all the propaganda, is how few Americans actually live this way.”
—Louise Kapp Howe (b. 1934)