%0 Generic
%D 2003
%T Complexity classes in models of cellular computing with membranes
%A Mario J. Pérez-Jiménez
%A Álvaro Romero-Jiménez
%A Fernando Sancho-Caparrini
%C Amsterdam, Netherlands
%I Springer Verlag
%K Complexity Classes
%K Membrane computing
%K P systems
%N 3
%P 265 - 285
%R 10.1023/A:1025449224520
%U http://dx.doi.org/10.1023/A:1025449224520
%V 2
%X 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.