科研之友
微信
新浪微博
Facebook
分享链接
摘要
Obtaining all of the truth assignments of SAT is called All-SAT and it has numerous applications in artificial intelligence and computer theories. Many algorithms about SAT have been built, but how to solve All-SAT is still difficult. P system is a kind of distributed parallel computing device of a biochemical type, and membrane division is one of frequently investigated way for obtaining exponential working space in a leaner time (membranes can be repeatedly divided to 2n ones in n steps). In this paper, we give a family of uniform P systems with active membranes and polarizations to solve All-SAT problem simultaneously in polynomial time. Instances show that our P systems can provide all solutions for SAT problems effectively in a distributed and parallel manner.
- 出版日期2016-7
- 单位浙江大学
