Abstract
A P system is a natural computing model inspired by information processes in cells and a control role of cellular membranes. We show that uniform families of P systems with active membranes are able to solve, in polynomial time, exactly the class of decisional problems PSPACE. Similar results were achieved also with other models of bio-inspired computers, such as DNA computing. Together they suggest that PSPACE naturally characterizes the computational potential of biological information processing.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Păun, G.: Computing with Membranes. J. Comput. System Sci. 61, 108–143 (2000)
Păun, G.: Membrane Computing: an Introduction. Springer, Berlin (2002)
The P Systems Web Page at http://psystems.disco.unimib.it
Păun, G.: P systems with active membranes: attacking NP complete problems. J. Automata, Languages and Combinatorics 6(1), 75–90 (2001)
Alhazov, A., Freund, R., Riscos-Núñez, A.: One and two polarizations, membrane creation and objects complexity in P systems. In: Ciobanu, G., Păun, G. (eds.) First Int. Workshop on Theory and Application of P Systems (TAPS), Timişoara, Romania, pp. 9–18 (2005)
Alhazov, A., Martin-Vide, C., Pan, L.: Solving a PSPACE-complete problem by P systems with restricted active membranes. Fundamenta Informaticae 58(2), 67–77 (2003)
Ciobanu, G., Pan, L., Păun, G., Pérez-Jiménez, M.J.: P Systems with Minimal Parallelism (submitted)
Pérez–Jiménez, M.J., Gutiérrez–Naranjo, M.A., Riscos–Núñez, A., Romero–Campero, F.J.: On the Power of Dissolution in P Systems with Active Membranes. In: Freund, R., et al. (eds.) WMC 2005. LNCS, vol. 3850, pp. 224–240. Springer, Heidelberg (2006)
Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-Núñez, A., Romero-Campero, F.J.: Characterizing standard tractability by cell-like membrane systems. In: Subramanian, K.G. (ed.) Formal Models, Languages and Applications, World Scientific, Singapore (in press, 2006)
Pérez-Jiménez, M.J., Jiménez, A.R., Sancho-Caparrini, F.: Complexity classes in models of cellular computing with membranes. Natural Computing 2, 265–285 (2003)
Sosík, P.: The computational power of cell division: beating down parallel computers? Natural Computing 2–3, 287–298 (2003)
Zandron, C., Ferretti, C., Mauri, G.: Solving NP-complete problems using P systems with active membranes. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, pp. 289–301. Springer, London (2000)
Balcazar, J.L., Diaz, J., Gabarro, J.: Structural Complexity II. Springer, Berlin (1991)
Beaver, D.: A universal molecular computer. In: Lipton, R.J., Baum, E.B. (eds.) DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, vol. 27, pp. 29–36 (1995)
Dantsin, E., Wolpert, A.: A robust DNA computation model that captures PSPACE. Int. J. Foundations Comp. Sci. 14(5), 933–951 (2003)
Pudlák, P.: Complexity theory and genetics: The computational power of crossing-over. Information and Computation 171, 201–223 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sosík, P., Rodríguez-Patón, A. (2006). P Systems with Active Membranes Characterize PSPACE. In: Mao, C., Yokomori, T. (eds) DNA Computing. DNA 2006. Lecture Notes in Computer Science, vol 4287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11925903_3
Download citation
DOI: https://doi.org/10.1007/11925903_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49024-1
Online ISBN: 978-3-540-68423-7
eBook Packages: Computer ScienceComputer Science (R0)