Characterising the complexity of tissue P systems with fission rules
作者：
Highlights：
• We analyse the computational efficiency of tissue P systems with fission rules (cell division and/or cell separation).
• Only coarse lower and upper bounds for the class of problems solvable in polynomial time by these P systems were known.
• We prove tight bounds, and exactly characterise the above class showing that it coincides with P#P, the class of problems solved by polynomial-time Turing machines with oracles for counting problems.
• This result holds for deterministic as well as for nondeterministic confluent tissue P systems.
摘要
•We analyse the computational efficiency of tissue P systems with fission rules (cell division and/or cell separation).•Only coarse lower and upper bounds for the class of problems solvable in polynomial time by these P systems were known.•We prove tight bounds, and exactly characterise the above class showing that it coincides with P#P, the class of problems solved by polynomial-time Turing machines with oracles for counting problems.•This result holds for deterministic as well as for nondeterministic confluent tissue P systems.
论文关键词：Membrane computing,Computational complexity,Tissue P systems,Counting complexity,Cell fission
论文评审过程：Received 30 August 2016, Revised 28 May 2017, Accepted 20 June 2017, Available online 21 July 2017, Version of Record 14 September 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.06.008
