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 playing adult steps sideward into another reality; the playing child advances forward to new stages of mastery....Child’s play is the infantile form of the human ability to deal with experience by creating model situations and to master reality by experiment and planning.”
—Erik H. Erikson (20th century)