Journal
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Volume 90, Issue -, Pages 115-128Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2017.06.008
Keywords
Membrane computing; Computational complexity; Tissue P systems; Counting complexity; Cell fission
Funding
- Fondo d'Ateneo (FA) of Universita degli Studi di Milano-Bicocca: Complessita computazionale e applicazioni crittografiche di modelli di calcolo bioispirati
Ask authors/readers for more resources
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. (C) 2017 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available