Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437916 | Theoretical Computer Science | 2010 | 10 Pages |
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