Journal of Computer and System Sciences 73 (2007) 137152
www.elsevier.com/locate/jcss
Membrane computing and complexity theory:
A characterization of PSPACE
Petr Sosk
a,b,
, Alfonso Rodrguez-Patn
a
a
Departamento de Inteligencia Artical, Facultad de Informtica, Universidad Politcnica de Madrid, Campus de Montegancedo s/n,
Boadilla del Monte, 28660 Madrid, Spain
b
Institute of Computer Science, Silesian University, 74601 Opava, Czech Republic
Received 29 May 2006; received in revised form 3 October 2006
Available online 7 November 2006
Abstract
A P system is a natural computing model inspired by information processing in cells and cellular membranes. We show that
conuent P systems with active membranes solve in polynomial time exactly the class of problems PSPACE. Consequently, these
P systems prove to be equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer.
Similar results were achieved also with other models of natural computation, such as DNA computing or genetic algorithms. Our
result, together with the previous observations, suggests that the class PSPACE provides a tight upper bound on the computational
potential of biological information processing models.
2006 Elsevier Inc. All rights reserved.
Keywords: Biological computation; P system; PSPACE; Alternating Turing machine
1. Introduction
Membrane systems, called also P systems, are bio-inspired computing models belonging to a broader family of so-
called biological or natural computing. Besides established natural computing topics like articial neural networks,
genetic algorithms, ant algorithms, DNA computing etc., P systems are trying to capture computational aspects of
cell metabolism and information interchange. Particularly, they focus on selective particle recognition by membranes,
controlled transport through protein channels, cell metabolism or membrane division and dissolution. These processes
are modeled in P systems by means of parallel multiset processing in separate cell-like regions. The aim of these
models is to identify operations which give to cellular systems their information-processing strength and to prepare
their possible implementation in vitro or in silico.
This motivation is complemented by recent successful attempts to use P systems as models of biological phenom-
ena, especially in situations with a low molecule concentration. Preliminary results can be found in [5], modeling
phenomena as mechanosensitive channels, bacteria respiration, photosynthesis or the p53 signaling pathways.
Expanded version of a paper presented at the 12th Int. Meeting on DNA Computing (DNA 12).
*
Corresponding author.
E-mail addresses: petr.sosik@fpf.slu.cz (P. Sosk), arpaton@.upm.es (A. Rodrguez-Patn).
0022-0000/$ see front matter 2006 Elsevier Inc. All rights reserved.
doi:10.1016/j.jcss.2006.10.001
