A Linear-Time Solution for All-SAT Problem Based on P System
A Linear-Time Solution for All-SAT Problem Based on P System作者机构：College of Computer Science Chongqing University Chongqing Key Laboratory of Software Theory and Technology Department of Software Engineering Chongqing College of Electronic Engineering
出 版 物：《Chinese Journal of Electronics》 (电子学报(英文))
年 卷 期：2018年第27卷第2期
页 面：367-373页
核心收录：
学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：supported by the Fundamental Research Funds for the Central Universities(No.CDJZR121800002) Chongqing Natural Science Foundation(No.cstc2013jcyj A40046) the National Natural Science Foundation of China(No.61201347)
主 题：Membrane computing Cell-like P systems Boolean Satisfiability problem(SAT problem) Find All solutions of SAT(All-SAT) problem
摘 要：P system is a new kind of distributed parallel computing model, and its many variants are used to solve NP problems. All-SAT problem is a well-known NPhard problem and it has been widely applied in the fields of pro ject selection problem, capital budgeting problem and so on. In this paper, we present a family of P systems to solve All-SAT problem in a linear time based on membrane division and give an instance to illustrate the feasibility and effectiveness of our designed P systems.
同方期刊数据库