Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951144 | Journal of Computer and System Sciences | 2017 | 19 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron,