Counting Membrane Systems

Abstract

A decision problem is one that has a yes/no answer, while a counting problem asks how many possible solutions exist associated with each instance. Every decision problem X has associated a counting problem, denoted by #X, in a natural way by replacing the question “is there a solution?” with “how many solutions are there?”. Counting problems are very attractive from a computational complexity point of view: if X is an NP-complete problem then the counting version #X is NP-hard, but the counting version of some problems in class P can also be NP-hard. In this paper, a new class of membrane systems is presented in order to provide a natural framework to solve counting problems. The class is inspired by a special kind of non-deterministic Turing machines, called counting Turing machines, introduced by L. Valiant. A polynomial-time and uniform solution to the counting version of the SAT problem (a well-known #P-complete problem) is also provided, by using a family of counting polarizationless P systems with active membranes, without dissolution rules and division rules for non-elementary membranes but where only very restrictive cooperation (minimal cooperation and minimal production) in object evolution rules is allowed.