Research Group on Natural Computing

In this paper we introduce four complexity classes for cellular computing systems with membranes: the first and the second ones contain all decision problems solvable in polynomial time by a family of deterministic P systems, without and with an input membrane, respectively; the third and fourth classes contain all decision problems solvable in polynomial time by a family of non-deterministic P systems, without and with an input membrane, respectively. We illustrate the usefulness of these classes by solving two NP–complete problems, namely HPP and SAT, in both variants of P systems.