Complexity classes in models of cellular computing with membranes

TitleComplexity classes in models of cellular computing with membranes
Publication TypeJournal Papers
Year of Publication2003
AuthorsPérez-Jiménez, M. J., Romero-Jiménez Á., & Sancho-Caparrini F.
Journal TitleNatural Computing
PublisherSpringer Verlag
Place PublishedAmsterdam, Netherlands
Volume2
Pages265 - 285
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.

KeywordsComplexity Classes, Membrane computing, P systems
URLhttp://dx.doi.org/10.1023/A:1025449224520
Issue3
ISSN Number1567-7818
DOI10.1023/A:1025449224520