We consider a variant of P systems called elimination P systems. These are polarizationless P systems with active membranes having no non-elementary membrane division rules, extended with rules of the form \([ab\rightarrow \varepsilon ]_h\) , where a and b are objects and \(\varepsilon\) denotes the empty word. The semantics of these rules are as follows: when a and b are present together within the same membrane with label h, they are both eliminated and no new objects are produced. We investigate the computational power of two types of elimination P systems designed to solve decision problems. In recognizer elimination P systems, as usual, an accepting computation must output a single yes object, and a rejecting computation must output one no object, both occurring precisely in the final step of the computation. In the more general extended acknowledger elimination P systems, an accepting computation should produce one or more yes objects, whereas a rejecting computation should not produce any yes objects. Our main result is that while recognizer elimination P systems with no dissolution rules can solve in polynomial-time only problems in \({\textbf {NL}}\) , extended acknowledger elimination P systems with no dissolution rules are able to solve \({\textbf {PP}}\) -complete problems. This demonstrates the importance of the definition of accepting conditions in these P systems.
