In this paper we present a method for solving the {\bf NP}-complete SAT problem using the type of P systems that is defined in \cite{manu}. The SAT problem is solved in $O(nm)$ time, where $n$ is the number of boolean variables and $m$ is the number of clauses for a instance written in conjunctive normal form. Thus we can say that the solution for each given instance is obtained in linear time. We succeeded in solving SAT by a uniform construction of a deterministic P system which uses rules involving objects in regions, proteins on membranes, and membrane division. We also investigate the computational power of these systems and show that the universality can be reached even in the case of systems that do not even use the membrane division and have only one membrane.
|
|