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:
“I had a wonderful job. I worked for a big model agency in Manhattan.... When I got on the subway to go to work, it was like traveling into another world. Oh, the shops were beautiful, we had Bergdorf’s, Bendel’s, Bonwit’s, DePinna. The women wore hats and gloves. Another world. At home, it was cooking, cleaning, taking care of the kids, going to PTA, Girl Scouts. But when I got into the office, everything was different, I was different.”
—Estelle Shuster (b. c. 1923)