Computational complexity in P systems

• Prof. Mario de J. Pérez Jiménez, Facultad de Matemáticas, Universidad de Sevilla, Spain

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

1. A. Alhazov, L. Pan, Gh. Paun: Trading polarizations for labels in P systems with active membranes. Acta Informaticae, 41, 2-3 (2004), 111-144.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. N. Murphy, D. Woods: A characterisation of \(NL\) using membrane systems without charges and dissolution. Lecture Notes in Computer Science, 5204 (2008), 164–176.
10. A. Obtulowicz: Deterministic P systems for solving {\sc SAT} problem. Romanian Journal of Information Science and Technology, 4, 1–2 (2001), 551–558.
11. Gh. Paun: P systems with active membranes: Attacking NP–complete problems. Journal of Automata, Languages and Combinatorics, 6, 1 (2001), 75–90.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. A.E. Porreca, G. Mauri, C. Zandron: Complexity classes for membrane systems. Informatique théorique et applications, 40, 2 (2006), 141–162.
21. P. Sosík: The computational power of cell division. Natural Computing, 2, 3 (2003), 287–298.
22. 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.
23. 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.

Sponsored by: Dr. Pierluigi Frisco, Heriot-Watt University, School of Mathematical and Computer Sciences, Edinburgh, UK

Reviewed by: Dr. Francisco J. Romero Campero, School of Computer Science and IT, University of Nottingham, UK

Reviewed by: Anonymous

Accepted on: 2009-10-13 11:55:32 GMT