We propose a membrane algorithm which solves the 3-SAT NP-complete problem. The algorithm uses membrane division to generate all possible assignments, and for each assignment it tests whether the set of clauses given in input are satisfied. Assignments are represented as n-bit binary numbers, on their turn represented by appropriate multisets, where n is the number of variables upon which the input clauses are defined. We claim that the solution scheme adopted in this paper is general enough to be applied to a very large class of NP-complete problems. Our encoding of binary numbers makes it also promising to solve NP-complete numerical problems, such as Knapsack, Subset Sum and Partition.
Leporati, A., Zandron, C. (2005). A family of P systems which solve 3-SAT. In Cellular Computing (Complexity Aspect), ESF PESC Exploratory Workshop (pp.247-256). Seville : Fénix Editora.
A family of P systems which solve 3-SAT
LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO
2005
Abstract
We propose a membrane algorithm which solves the 3-SAT NP-complete problem. The algorithm uses membrane division to generate all possible assignments, and for each assignment it tests whether the set of clauses given in input are satisfied. Assignments are represented as n-bit binary numbers, on their turn represented by appropriate multisets, where n is the number of variables upon which the input clauses are defined. We claim that the solution scheme adopted in this paper is general enough to be applied to a very large class of NP-complete problems. Our encoding of binary numbers makes it also promising to solve NP-complete numerical problems, such as Knapsack, Subset Sum and Partition.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
