Ponencia
Counting Membrane Systems
Autor/es | Valencia Cabrera, Luis
Orellana Martín, David Riscos Núñez, Agustín Pérez Jiménez, Mario de Jesús |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2017 |
Fecha de depósito | 2019-03-29 |
Publicado en |
|
Resumen | 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 ... 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. |
Cita | Valencia Cabrera, L., Orellana Martín, D., Riscos Núñez, A. y Pérez Jiménez, M.d.J. (2017). Counting Membrane Systems. En CMC 2018 : 18th International Conference on Membrane Computing (359-372), Bradford, UK: University of Bradford, Faculty of Engineering and Informatics. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
articulo-counting-membrane-sys ... | 505.7Kb | [PDF] | Ver/ | |