@article {114,
	title = {Complexity classes in models of cellular computing with membranes},
	journal = {Natural Computing},
	volume = {2},
	year = {2003},
	pages = {265 - 285   },
	publisher = {Springer Verlag},
	address = {Amsterdam, Netherlands},
	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{\textendash}complete problems, namely HPP and SAT, in both variants of P systems.



},
	keywords = {Complexity Classes, Membrane computing, P systems},
	issn = {1567-7818 },
	doi = {10.1023/A:1025449224520},
	url = {http://dx.doi.org/10.1023/A:1025449224520},
	author = {Mario J. P{\'e}rez-Jim{\'e}nez and {\'A}lvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}
}
