On determinism versus nondeterminism in P systems

AbstractAn important open problem in the area of membrane computing is whether there is a model of P systems for which the nondeterministic version is strictly more powerful than the deterministic version. We resolve this problem in the following sense—we exhibit two classes of P system acceptors with only communicating rules and show:1.For the first class, the deterministic and nondeterministic versions are equivalent if and only if deterministic and nondeterministic linear bounded automata are equivalent. The latter problem is a long-standing open question in complexity theory.2.For the second class, the deterministic version is strictly weaker than the nondeterministic version.Both classes are nonuniversal, but can accept fairly complex languages