科研之友
微信
新浪微博
Facebook
分享链接
摘要
We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide all algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slow-down. Together, these results prove that the complexity class of problems solvable nonconfluently and in polynomial time by this kind of P system is exactly the class NP.
- 出版日期2010-2-6
