Simulating elementary active membranes with an application to the P conjecture

5noThe decision problems solved in polynomial time by P systems with elementary active membranes are known to include the class ^#. This consists of all the problems solved by polynomial-time deterministic Turing machines with polynomial-time counting oracles. In this paper we prove the reverse inclusion by simulating P systems with this kind of machines: this proves that the two complexity classes coincide, finally solving an open problem by Păun on the power of elementary division. The equivalence holds for both uniform and semi-uniform families of P systems, with or without membrane dissolution rules. Furthermore, the inclusion in ^# also holds for the P systems involved in the P conjecture (with elementary division and dissolution but no charges), which improves the previously known upper bound .nonenoneLeporati Alberto; Manzoni Luca; Mauri Giancarlo; Porreca Antonio E.; Zandron ClaudioLeporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca Antonio, E.; Zandron, Claudi