We analyse the computational efficiency of tissue P systems, a biologically-inspired computing device modelling the communication between cells. In particular, we focus on tissue P systems with fission rules (cell division and/or cell separation), where the number of cells can increase exponentially during the computation. We prove that the complexity class characterised by these devices in polynomial time is exactly P^#P, the class of problems solved by polynomial-time Turing machines with oracles for counting problems.

Characterising the complexity of tissue P systems with fission rules

Manzoni Luca;
2017-01-01

Abstract

We analyse the computational efficiency of tissue P systems, a biologically-inspired computing device modelling the communication between cells. In particular, we focus on tissue P systems with fission rules (cell division and/or cell separation), where the number of cells can increase exponentially during the computation. We prove that the complexity class characterised by these devices in polynomial time is exactly P^#P, the class of problems solved by polynomial-time Turing machines with oracles for counting problems.
2017
Pubblicato
https://www.sciencedirect.com/science/article/pii/S0022000017301083
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0022000017301083-main.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 447.01 kB
Formato Adobe PDF
447.01 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2947806_1-s2.0-S0022000017301083-main-PostPrint.pdf

accesso aperto

Descrizione: Post Print VQR3
Tipologia: Bozza finale post-referaggio (post-print)
Licenza: Digital Rights Management non definito
Dimensione 908.79 kB
Formato Adobe PDF
908.79 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11368/2947806
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 18
social impact