Shallow non-confluent P systems

5noWe prove that non-confluent (i.e., strongly nondeterministic) P systems with active membranes working in polynomial time are able to simulate polynomial-space nondeterministic Turing machines, and thus to solve all problems. Unlike the confluent case, this result holds for shallow P systems. In particular, depth 1 (i.e., only one membrane nesting level and using elementary membrane division only) already suffices, and neither dissolution nor send-in communication rules are needed.reservedmixedLeporati Alberto; Manzoni Luca; Mauri Giancarlo; Porreca Antonio E.; Zandron ClaudioLeporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca Antonio, E.; Zandron, Claudi