Artículo
Polarizationless P Systems with Active Membranes: Computational Complexity Aspects
Autor/es | Valencia Cabrera, Luis
Orellana Martín, David Martínez del Amor, Miguel Ángel 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 | 2016 |
Fecha de depósito | 2021-12-01 |
Publicado en |
|
Resumen | P systems with active membranes, in their classical definition, make use of noncooperative
rules only. However, it is well known that in living cells, proteins interact
among them yielding new products. Inspired by this ... P systems with active membranes, in their classical definition, make use of noncooperative rules only. However, it is well known that in living cells, proteins interact among them yielding new products. Inspired by this biological phenomenon, the previous framework is reformulated in this paper, allowing cooperation in object evolution rules, while removing electrical charges associated with membranes. More precisely, minimal cooperation in object evolution rules is incorporated in polarizationless P systems with active membranes. In this paper, the term “minimal” means that the left-hand side of such rules consists of at most two symbols, and its length is greater than or equal to the corresponding right-hand side. The computational efficiency of this kind of P systems is studied by providing a uniform polynomial-time solution to SAT problem in such manner that only division rules for elementary membranes are used and dissolution rules are forbidden. Bearing in mind that only tractable problems can be efficiently solved by families of polarizationless P systems with active membranes and without dissolution rules, passing from non-cooperation to minimal cooperation in object evolution rules amounts passing from non-efficiency to efficiency in this framework. This frontier of efficiency provides, as any other borderline does, a possible way to address the P versus NP problem. |
Agencias financiadoras | National Natural Science Foundation of China |
Identificador del proyecto | No. 61033003
No. 61320106005 |
Cita | Valencia Cabrera, L., Orellana Martín, D., Martínez del Amor, M.Á., Riscos Núñez, A. y Pérez Jiménez, M.d.J. (2016). Polarizationless P Systems with Active Membranes: Computational Complexity Aspects. Journal of Automata, Languages and Combinatorics, 21 (1-2), 107-123. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
JALC-2016-articulo-publicado.pdf | 557.5Kb | [PDF] | Ver/ | |