P Systems with Proteins on Membranes and Membrane Division

Andrei PAUN, Bianca POPA


Abstract

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.


Server START Conference Manager
Update Time 20 Feb 2006 at 20:05:03
Maintainer zdang@eecs.wsu.edu.
Start Conference Manager
Conference Systems