# Computational complexity in P systems

Mario de J. Pérez Jiménez (2009), Scholarpedia, 4(11):9290. | doi:10.4249/scholarpedia.9290 | revision #91148 [link to/cite this article] |

## Contents |

## Recognizer P systems

Complexity theory deals with *decision problems*, yes-or-no answer problems. Formally, a *decision problem*, \(X\ ,\) is defined as a pair \((I_{X},\theta_{X})\)
such that \(I_{X}\) is a language over a finite alphabet (whose elements
are called *instances*) and \(\theta_{X}\) is a total boolean function over \(I_{X}\ .\) A language,\(L_X\ ,\) is naturally associated to every decision problem, \(X\ ,\) as the set of instances for which a positive answer is provided, \(L_X=\{w \in I_X: \ \theta_X(w)=1\}\)).

The solvability of decision problems is defined through the recognition of the languages associated with them (every decision problem \(X=(I_X, \theta_X)\ ,\) has associated a language \(L_X=\{w \in I_X: \ \theta_X(w)=1\}\)).

A *recognizer P system* is a P system such that: (a)
the working alphabet contains two distinguished elements *yes*
and *no*; (b) all computations halt; and (c) in the last step of every computation of the system and never in any previous step, either the object *yes* or the object *no* (but not both) must have been sent to the output region of the system.

### Uniform families of P systems

Many formal machine models (e.g. Turing machines or register machines) have an infinite number of memory locations. In contrast, P systems, likewise logic circuits, are computing devices of finite size that can be described with a fixed amount of initial resources (number of membranes, objects, gates, etc.). According to this, in order to solve a decision problem a (possibly infinite) family of P systems needs to be considered.

A P system with input membrane is a tuple \((\Pi, \Sigma, i_{in})\) where: (a)\(\Pi\) is a P system with working alphabet \(\Gamma\ ;\) (b)\(\Sigma\) is an (input) alphabet strictly contained in \(\Gamma\) such that the initial multisets of \(\Pi\) are over the alphabet \(\Gamma \setminus \Sigma\ ;\) and (c) \(i_{in}\) is the label of a distinguished (input) membrane.

In the case of P systems with input membrane, the term uniform family is consistent with the usual meaning for Boolean circuits: a family of such P systems \(\mathbf{\Pi} = \{\Pi(n): \ n \in \N\}\) is uniform if there exists a deterministic Turing machine which constructs the system \(\Pi(n)\) from \(n \in \N\) (that is, which on input \(1^n\) outputs \(\Pi(n)\)).

In the case of P systems without input membrane a new notion arises: a
family \(\mathbf{\Pi} = \{\Pi(w): \ w \in I_X \}\) *associated with a decision problem* \(X=(I_X, \theta_X)\) is *uniform* if there
exists a deterministic Turing machine which constructs the system
\(\Pi(w)\) from the instance \(w \in I_X\ .\)

Concepts of uniformity below P are considered by N. Murphy and D. Woods (2008, ref.9).

In (2003, ref. 21, and 2007 ref. 22) P. Sosik et al. presented an (apparently) different concept of uniform families of P systems: each member of the family is said to be constructed by a specific deterministic Turing machine.

### Confluent P systems

In order for recognizer P systems to capture the true algorithmic
concept, a condition of *confluence* is imposed, in the sense that
all possible successful computations must give the same answer. This
contrasts with the standard notion of accepting computations for
non-deterministic (classic) models.

Let \(X = (I_X, \theta_X)\) be a decision problem, and \(\mathbf{\Pi} = \{\Pi(w): \ w \in I_X \}\) be a family of recognizer P systems without input membrane.

- \(\mathbf{\Pi}\) is said to be
*sound with respect to \(X\)*if the following holds: for each instance of the problem, \(w \in I_X\ ,\) if*there exists*an accepting computation of \(\Pi(w)\ ,\) then \(\theta_X (w) = 1\ .\) - \(\mathbf{\Pi}\) is said to be
*complete with respect to \(X\)*if the following holds: for each instance of the problem, \(w \in I_X\ ,\) if \(\theta_X (w)= 1\ ,\) then*every*computation of \(\Pi(w)\) is an accepting computation.

The concepts of soundness and completeness can be extended to
families of recognizer P systems with input membrane in a natural
way.

Let \(X = (I_X, \theta_X)\) be a decision problem, and \(\mathbf{\Pi} =
\{\Pi(n): \ n \in \N\}\) a family of recognizer P systems with input
membrane. A *polynomial encoding* of \(X\) in \(\mathbf{\Pi}\) is a
pair \((cod, s)\) of polynomial–time computable functions over \(I_X\)
such that for each instance \(w \in I_X\ ,\) \(s(w)\) is a natural number
(obtained by means of a reasonable encoding scheme) and \(cod(w)\) is
an input multiset of the system \(\Pi (s(w))\ .\)

Let \(X = (I_X, \theta_X)\) be a decision problem, \(\mathbf{\Pi} = \{\Pi(n): \ n \in \N\}\) a family of recognizer P systems with input membrane, and \((cod, s)\) a polynomial encoding of \(X\) in \(\mathbf{\Pi}\ .\)

- \(\mathbf{\Pi}\) is said to be
*sound with respect to \((X, cod, s)\)*if the following holds: for each instance of the problem, \(w \in I_X\ ,\) if*there exists*an accepting computation of \(\Pi(s(w))\) with input \(cod(w)\ ,\) then \(\theta_X (w) = 1\ .\) - \(\mathbf{\Pi}\) is said to be
*complete with respect to \((X, cod, s)\)*if the following holds: for each instance of the problem, \(w \in I_X\ ,\) if \(\theta_X (w)= 1\ ,\) then*every*computation of \(\Pi(s(w))\) with input \(cod(w)\) is an accepting computation.

## Polynomial complexity classes in Membrane Computing

The first results showing that membrane systems
could solve computationally hard problems in polynomial time were obtained
using P systems without input membrane. In that context, a specific P system
is associated with each instance of the problem. In other words, the
syntax of the instance is part of the description of the associated P system.
Thus, this P system can be considered *special purpose*.

A decision problem \(X\) is *solvable in polynomial time* by a family of recognizer P systems without input
membrane \(\mathbf{\Pi} = \{\Pi(w): \ w \in I_X \}\ ,\) denoted by \(X
\in \mathbf{PMC}^*_{\mathcal{R}}\ ,\) if the following holds:

- The family \(\mathbf{\Pi}\) is polynomially uniform by Turing machines.
- The family \(\mathbf{\Pi}\) is polynomially bounded; that is, there exists a natural number \(k \in \N\) such that for each instance \(w \in I_X\ ,\) every computation of \(\Pi(w)\) performs at most \(|w|^k\) steps.
- The family \(\mathbf{\Pi}\) is sound and complete with respect to \(X\ .\)

The family \(\mathbf{\Pi}\) is said to provide a *semi–uniform solution* to the problem \(X\ .\)

Next, recognizer P systems with input membrane are defined to solve
problems in a *uniform* way in the following sense: all
instances of a decision problem of the same *size* (via a given
reasonable encoding scheme) are processed by the same system, to
which an appropriate input is supplied.

A decision problem \(X = (I_X, \theta_X)\) is *solvable in polynomial time* by a family of recognizer P systems with input
membrane \(\mathbf{\Pi} = \{\Pi(n): n \in \N \}\ ,\) denoted
by \(X \in \mathbf{PMC}_{\mathcal{R}}\ ,\) if the following holds:

- The family \(\mathbf{\Pi}\) is polynomially uniform by Turing machines.
- There exists a polynomial encoding \((cod, s)\) of \(X\) in \(\mathbf{\Pi}\) such that:
- The family \(\mathbf{\Pi}\) is polynomially bounded with respect to \((X, cod, s)\ ;\) that is, there exists a natural number \(k \in \N\) such that for each instance \(w \in I_X\ ,\) every computation of the system \(\Pi(s(w))\) with input \(cod(w)\) performs at most \(|w|^k\) steps.
- The family \(\mathbf{\Pi}\) is sound and complete with respect to \((X, cod, s)\ .\)

The family \(\mathbf{\Pi}\) is said to provide a *uniform solution* to the problem \(X\ .\)

As a direct consequence of working with recognizer membrane systems, these complexity classes are closed under complement. Moreover, they are closed under polynomial–time reductions (Pérez-Jiménez et al. 2003, ref. 16).

**Remark:**
It is interesting to distinguish the concept of *polynomially uniform by Turing machines* from the concepts of *semi–uniform*
and *uniform* solutions. The first concept is related with the
resources required to construct the family of P systems solving a
decision problem. The last two refer to the way in which the family
processes the instances. In semi-uniform solutions, every instance is
processed by a special purpose P system. While in uniform solutions,
each P system processes all instances of a given size.

## Efficiency of Basic Transition P Systems

A *basic transition* P system is a restricted variant only containing evolution, communication and dissolution rules. Consequently, these systems are unable to increase the size of the membrane structure. Let \(\mathcal{T}\) denote the class of
recognizer basic transition P systems.

M.A. Gutiérrez–Naranjo et al. (2006, ref. 7) gave an efficient
simulation of deterministic Turing machines by recognizer basic
transition P systems: *every deterministic Turing machine working in polynomial time can be simulated in polynomial time by a family of recognizer basic transition P systems with input membrane.*

They also proved that each confluent basic transition P system can be (efficiently) simulated by a deterministic Turing machine (M.A. Gutiérrez–Naranjo et al. 2006, ref. 7). As a consequence, these P systems efficiently solve at most tractable problems.

Moreover, a deterministic P system with active membranes but without membrane division can be simulated by a deterministic Turing machine with a polynomial slowdown (Milano Theorem). Hence, \(\mathbf{P}=\mathbf{PMC}_{\mathcal{T}}=\mathbf{PMC}^*_{\mathcal{T}}\ .\)
Thus, the ability of a P system in \(\mathcal{T}\) to
create exponential workspace (in terms of number of objects)
in polynomial time is not enough to efficiently solve **NP**–complete problems (unless **P** \(=\) **NP**).

## P Systems with Active Membranes

P systems with active membranes having associated electrical charges with membranes were first introduced by Gh. Paun (2001, ref. 11). Replication is one of the most important functions of a cell and, in ideal circumstances, a cell produces two identical copies by division (mitosis). Bearing in mind that the reactions which take place in a cell are related to membranes, rules for membrane division are considered.

In the framework of P systems without input membrane, C. Zandron et al. (2000, ref. 22) proved that deterministic recognizer P systems with active membranes without membrane division, can be efficiently simulated by a deterministic Turing machine (Milano theorem). Thus, if \(\mathcal{NAM}\) is the class of recognizer P systems with active membranes which do not make use of division rules, then \(\mathbf{P}=\mathbf{PMC}_{\mathcal{NAM}}=\mathbf{PMC}^*_{\mathcal{NAM}}\ .\)

The first efficient solutions to **NP**–complete problems by using
P systems with active membranes were given in a *semi–uniform* way
(where the P systems of the family depend on the syntactic structure
of the instance) by S.N. Krishna et al. (*Hamiltonian Path*,
*Vertex Cover*, 1999, ref. 8), A. Obtulowicz (*SAT*, 2001, ref. 10),
Gh. Paun (*SAT*, 2000 and 2001, ref. 11, 12), and C. Zandron et al. (*SAT* and *Undirected Hamiltonian Path*, 2000, ref. 22).

Let \(\mathcal{AM}(+n)\) (respectively, \(\mathcal{AM}(-n)\)) be the class of recognizer P systems with active membranes using division rules for elementary and non–elementary membranes (respectively, only for elementary membranes).

In the framework of \(\mathcal{AM}(-n)\ ,\) efficient *uniform*
solutions to weakly **NP**–complete problems (*Knapsack*, Pérez-Jiménez et al. 2004, ref. 15, *Subset Sum*, Pérez-Jiménez et al. 2005, ref.14, *Partition*,
Gutiérrez-Naranjo et al, 2005, ref. 5), and strongly **NP**–complete problems
(*SAT*, Pérez-Jiménez et al. 2003, ref. 19, *Clique*, Alhazov et al. 2004, ref. 2, *Bin Packing*, Pérez-Jiménez et al. 2004, ref. 18, *Common Algorithmic Problem*, Pérez-Jiménez et al. 2005, ref. 17)
have been obtained. Hence, **NP** \(\cup\)
**co-NP** \(\subseteq \mathbf{PMC}_{\mathcal{AM}(-n)}\ .\)

In the framework of \(\mathcal{AM} (+n)\ ,\) P. Sosík (2003, ref. 21) gave
an efficient *semi–uniform* solution to *QBF-SAT*
(satisfiability of quantified propositional formulas), a well known
**PSPACE**–complete problem (Garey and Johnson, 1979). Hence,
\(\mathbf{PSPACE} \subseteq \mathbf{PMC}^*_{\mathcal{AM} (+n)}\ .\)

This result has been extended by A. Alhazov et al. (2003, ref. 3)
showing that *QBF-SAT* can be solved in a linear time and in a
*uniform* way by a family of recognizer P systems with active
membranes (without using dissolution rules) and using division rules
for elementary and non–elementary membranes.

A.E. Porreca et al. (2006, ref.20) described a (deterministic and efficient) algorithm simulating a single computation of any confluent recognizer P system with active membranes and without input. Such P systems can be simulated by a deterministic Turing machine working with exponential space, and spending a time of the order \(O(2^{p(n)})\ ,\) for some polynomial \(p(n)\ .\) Thus, \(\mathbf{PSPACE} \subseteq \mathbf{PMC}_{\mathcal{AM}(+n)} \subseteq \mathbf{PMC}^*_{\mathcal{AM}(+n)} \subseteq \mathbf{EXP}\ .\)

### Polarizationless P systems with active membranes

The class of recognizer polarizationless P systems with active membranes allowing division rules only for elementary membranes is denoted by \(\mathcal{AM}^0 (+d, -n, +e, +c)\ .\)

At the beginning of 2005, Gh. Paun (problem **F** from
ref. 13) wrote:

*My favorite question (related to complexity aspects in P systems with active membranes and with electrical charges) is that about the number of polarizations. Can the polarizations be completely avoided? The feeling is that this is not possible – and such a result would be rather sound: passing from no polarization to two polarizations amounts to passing from non–efficiency to efficiency.*

This so–called Paun's conjecture can be formally
formulated in terms of membrane computing complexity classes as follows:
\[\mathbf{P} = \mathbf{PMC}_{\mathcal{AM}^0 (+d, -n, +e, +c)}=
\mathbf{PMC}^{*}_{\mathcal{AM}^0 (+d, -n, +e, +c)}\]

Let \(\Pi\) be a recognizer polarizationless P system with active
membranes which do not make use of dissolution rules.
A directed graph (*dependency graph*) can be associated with \(\Pi\) verifying the following property: every accepting computation of \(\Pi\) is characterized by the
existence of a path in the graph between two specific nodes.
Gutiérrez-Naranjo et al. 2006, ref. 6, showed that polarizationless P systems with
active membranes which do not make use of dissolution rules are
non--efficient in the sense that they cannot solve **NP**--complete
problems in polynomial time (unless **P**\(=\) **NP**).

Several authors (Alhazov et al. 2004, ref. 1, Gutiérrez-Naranjo et al. 2006, ref. 6) gave a positive answer when
division for non--elementary membranes, in the strong sense, is
permitted. The mentioned papers provide semi--uniform solutions in a
linear time to *SAT* and *Subset Sum*, respectively. Thus, a
*partial negative* answer to Paun's conjecture is given:
assuming that **P** \(\neq\) **NP** and making use of dissolution
rules and division rules for elementary and non–elementary membranes,
computationally hard problems can be efficiently solved avoiding
polarizations. The answer is partial because efficient solvability of
**NP**–complete problems by polarizationless P systems with active
membranes making use of dissolution rules and division *only* for
elementary membranes is unknown.

## References

- A. Alhazov, L. Pan, Gh. Paun: Trading polarizations for labels in P systems with active membranes.
*Acta Informaticae*,**41**, 2-3 (2004), 111-144. - A. Alhazov, C. Martín–Vide, L. Pan: Solving graph problems by P systems with restricted elementary active membranes.
*Lecture Notes in Computer Science*,**2950**(2004), 1–22. - A. Alhazov, C. Martín–Vide, L. Pan: Solving a PSPACE–complete problem by recognizing P systems with restricted active membranes.
*Fundamenta Informaticae*,**58**(2003), 67–77. - M.R. Garey, D.S. Johnson:
*Computers and Intractability. A guide to the theory of NP-completeness*. W.H. Freeman and Company, New York, 1979. - M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Núñez: A fast P system for finding a balanced 2-partition.
*Soft Computing*,**9**, 9 (2005), 673–678. - M.A. Gutiérrez–Naranjo, M.J. Pérez–Jiménez, A. Riscos–Núñez, F.J. Romero–Campero: On the power of dissolution in P systems with active membranes.
*Lecture Notes in Computer Science*,**3850**(2006), 224–240. - M.A. Gutiérrez–Naranjo, M.J. Pérez–Jiménez, A. Riscos–Núñez, F.J. Romero–Campero, A. Romero–Jiménez: Characterizing tractability by cell–like membrane systems. In K.G. Subramanian, K. Rangarajan, M. Mukund (eds.)
*Formal models, languages and applications*, World Scientific, Singapore, 2006, pp. 137–154. - S.N. Krishna, R. Rama: A variant of P systems with active membranes: Solving NP–complete problems.
*Romanian Journal of Information Science and Technology*,**2**, 4 (1999), 357–367. - N. Murphy, D. Woods: A characterisation of \(NL\) using membrane systems without charges and dissolution.
*Lecture Notes in Computer Science*,**5204**(2008), 164–176. - A. Obtulowicz: Deterministic P systems for solving {\sc SAT} problem.
*Romanian Journal of Information Science and Technology*,**4**, 1–2 (2001), 551–558. - Gh. Paun: P systems with active membranes: Attacking
**NP**–complete problems.*Journal of Automata, Languages and Combinatorics*,**6**, 1 (2001), 75–90. - Gh. Paun: Computing with membranes: Attacking
**NP**–complete problems. In I. Antoniou, C.S. Calude, M.J. Dinneen (eds.)*Unconventional Models of Computation*, Springer, London, 2000, pp. 94–115. - Gh. Paun: Further twenty six open problems in membrane computing.
*Third Brainstorming Week on Membrane Computing*(M.A. Gutiérrez et al. eds.), Fénix Editora, Sevilla, 2005, pp. 249–262. - M.J. Pérez-Jiménez, A. Riscos-Núñez: Solving the Subset-Sum problem by active membranes.
*New Generation Computing*,**23**, 4 (2005), 367–384. - M.J. Pérez-Jiménez, A. Riscos-Núñez: A linear–time solution to the Knapsack problem using P systems with active membranes.
*Lecture Notes in Computer Science*,**2933**(2004), 250–268. - M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini: A polynomial complexity class in P systems using membrane division.
*Proceedings of the Fifth International Workshop on Descriptional Complexity of Formal Systems*, Budapest, Hungary, July 12-14, 2003, pp. 284-294; and*Journal of Automata, Languages and Combinatorics*,**11**, 4 (2006), 423-434. - M.J. Pérez-Jiménez, F.J. Romero–Campero: Attacking the Common Algorithmic Problem by recognizer P systems.
*Lecture Notes in Computer Science*,**3354**(2005), 304–315. - M.J. Pérez–Jiménez, F.J. Romero–Campero: An efficient family of P systems for packing items into bins.
*Journal of Universal Computer Science*,**10**, 5 (2004), 650–670. - M.J. Pérez–Jiménez, A. Romero–Jiménez, F. Sancho–Caparrini: Complexity classes in cellular computing with membranes.
*Natural Computing*,**2**, 3 (2003), 265–285. - A.E. Porreca, G. Mauri, C. Zandron: Complexity classes for membrane systems.
*Informatique théorique et applications*,**40**, 2 (2006), 141–162. - P. Sosík: The computational power of cell division.
*Natural Computing*,**2**, 3 (2003), 287–298. - P. Sosík, A. Rodríguez-Patón: Membrane Computing and Complexity Theory: A characterisation of PSPACE.
*Journal of Computer and Systems Science*,**73**, (2007), 137–152. - C. Zandron, C. Ferretti, G. Mauri: Solving NP–complete problems using P systems with active membranes. In I. Antoniou, C.S. Calude, M.J. Dinneen (eds.)
*Unconventional Models of Computation*, Springer, Berlin, 2000, pp. 289–301.

**Internal references**

- Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623.

- Howard Eichenbaum (2008) Memory. Scholarpedia, 3(3):1747.

- Paul M.B. Vitanyi (2009) Turing machine. Scholarpedia, 4(3):6240.