A Linear-Time Solution for All-SAT Problem Based on P System

GUO Ping; ZHU Jian; CHEN Haizhu; YANG Ruilong

doi:10.1049/cje.2018.01.008

GUO Ping, ZHU Jian, CHEN Haizhu, YANG Ruilong. A Linear-Time Solution for All-SAT Problem Based on P System[J]. Chinese Journal of Electronics, 2018, 27(2): 367-373. DOI: 10.1049/cje.2018.01.008

Citation:

GUO Ping, ZHU Jian, CHEN Haizhu, YANG Ruilong. A Linear-Time Solution for All-SAT Problem Based on P System[J]. Chinese Journal of Electronics, 2018, 27(2): 367-373. DOI: 10.1049/cje.2018.01.008

Citation:

GUO Ping, ZHU Jian, CHEN Haizhu, YANG Ruilong. A Linear-Time Solution for All-SAT Problem Based on P System[J]. Chinese Journal of Electronics, 2018, 27(2): 367-373. DOI: 10.1049/cje.2018.01.008

A Linear-Time Solution for All-SAT Problem Based on P System

Graphical Abstract

Graphical Abstract

Abstract

Abstract

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 project 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.