Article ID Journal Published Year Pages File Type
437916 Theoretical Computer Science 2010 10 Pages PDF
Abstract

We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class .

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics