Characterising the complexity of tissue P systems with fission rules

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.