Open AccessA Linear‐Time Solution for All‐SAT Problem Based on P System
Author(s) -
GUO Ping,
ZHU Jian,
CHEN Haizhu,
YANG Ruilong
Publication year - 2018
Publication title -
chinese journal of electronics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 25
eISSN - 2075-5597
pISSN - 1022-4653
DOI - 10.1049/cje.2018.01.008
Subject(s) - selection (genetic algorithm) , computer science , division (mathematics) , mathematical optimization , linear system , p system , theoretical computer science , mathematics , algorithm , artificial intelligence , arithmetic , mathematical analysis
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.