Title: Depth-two P systems can simulate Turing machines with NP oracles
Abstract: Among the computational features that determine the computing power of polarizationless P systems with active membranes, the depth of the membrane hierarchy is one of the least explored. It is known that this model of P systems can solve -complete problems when no constraints are given on the depth of the membrane hierarchy, whereas the complexity class P∥#P is characterized by monodirectional shallow P systems with minimal cooperation, whose depth is 1. No similar result is currently known for polarizationless systems without cooperation or other additional features. In this paper we show that these P systems, using a membrane hierarchy of depth 2, are able to solve at least all decision problems that are in the complexity class , the class of problems solved in polynomial time by deterministic Turing machines that are given the possibility to make a polynomial number of parallel queries to oracles for problems.