Membrane systems (also called P systems) are unconventional, parallel computing devices inspired by the internal working of biological cells. Some variants of membrane systems (in particular, P systems with elementary active membranes) have been known to be able to solve NP-complete problems in polynomial time by trading space for time, exploring in parallel the whole exponential-size space of candidate solutions. Here we provide a formal notion of space complexity for P systems, in order to be able to prove results about the computing power and limitations of P systems with active membranes working in bounded space. As a result, we show that P systems working in polynomial space solve exactly the same problem as Turing machines working in polynomial space. Furthermore, we show that P systems with elementary active membranes running in exponential space not only solve NP-complete problems in polynomial time, but also counting problems and the whole polynomial hierarchy.

(2012). The time-space trade-off in membrane computing. (Tesi di dottorato, Università degli Studi di Milano-Bicocca, 2012).

The time-space trade-off in membrane computing

PORRECA, ANTONIO ENRICO
2012

Abstract

Membrane systems (also called P systems) are unconventional, parallel computing devices inspired by the internal working of biological cells. Some variants of membrane systems (in particular, P systems with elementary active membranes) have been known to be able to solve NP-complete problems in polynomial time by trading space for time, exploring in parallel the whole exponential-size space of candidate solutions. Here we provide a formal notion of space complexity for P systems, in order to be able to prove results about the computing power and limitations of P systems with active membranes working in bounded space. As a result, we show that P systems working in polynomial space solve exactly the same problem as Turing machines working in polynomial space. Furthermore, we show that P systems with elementary active membranes running in exponential space not only solve NP-complete problems in polynomial time, but also counting problems and the whole polynomial hierarchy.
ZANDRON, CLAUDIO
theory of computation; computational complexity; membrane computing; natural computing
INF/01 - INFORMATICA
English
Scuola di dottorato di Scienze
INFORMATICA - 22R
24
2010/2011
(2012). The time-space trade-off in membrane computing. (Tesi di dottorato, Università degli Studi di Milano-Bicocca, 2012).
File in questo prodotto:
File Dimensione Formato  
Phd_unimib_053245.pdf

accesso aperto

Tipologia di allegato: Doctoral thesis
Dimensione 886.33 kB
Formato Adobe PDF
886.33 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/29222
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
Social impact