View Related Documents

Abstract

We prove that a uniform family of P systems with active membranes, where division rules only operate on elementary membranes and dissolution rules are avoided, can be used to solve the following PP-complete decision problem in polynomial time: given a Boolean formula of m variables in 3CNF, do at least Ö{2m}\sqrt{2^m} among the 2 m possible truth assignments satisfy it? As a consequence, the inclusion PP Í PMCAM(-d,-n)\mathbf{PP} \subseteq \mathbf{PMC}_{\mathcal{AM}(\mathrm{-d,-n})} holds: this provides an improved lower bound on the class of languages decidable by this kind of P systems.

Fulltext Preview

Image of the first page of the fulltext document