Summary: 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 \(\mathbf {NP}\)-complete problem then the counting version \(\#X\) is \(\mathbf {NP}\)-hard, but the counting version of some problems in class \({\mathbf P}\) can also be \(\mathbf {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 in 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 \(\#{\mathbf 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.
For the entire collection see [Zbl 1381.68008].