Complexity classes in models of cellular computing with membranes

Abstract:

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. © 2003 Kluwer Academic Publishers.

Año de publicación:

2003

Keywords:

• Membrane Computing
• P systems
• Complexity classes

Fuente:

scopus