Artículo
On a partial affirmative answer for a Paun's Conjecture
Autor/es | Pérez Hurtado de Mendoza, Ignacio
Pérez Jiménez, Mario de Jesús Riscos Núñez, Agustín Gutiérrez Naranjo, Miguel Ángel Rius Font, Miquel |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2011 |
Fecha de depósito | 2024-04-22 |
Publicado en |
|
Resumen | At the beginning of 2005, Gheorghe Pun formulated a conjecture stating that in the framework of recognizer P systems with active membranes (evolution rules, communication rules, dissolution rules and division rules for ... At the beginning of 2005, Gheorghe Pun formulated a conjecture stating that in the framework of recognizer P systems with active membranes (evolution rules, communication rules, dissolution rules and division rules for elementary membranes), polarizations cannot be avoided in order to solve computationally hard problems efficiently (assuming that P ≠ NP). At the middle of 2005, a partial positive answer was given, proving that the conjecture holds if dissolution rules are forbidden. In this paper we give a detailed and complete proof of this result modifying slightly the notion of dependency graph associated with recognizer P systems. |
Cita | Pérez Hurtado de Mendoza, I., Pérez Jiménez, M.d.J., Riscos Núñez, A., Gutiérrez Naranjo, M.Á. y Rius Font, M. (2011). On a partial affirmative answer for a Paun's Conjecture. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 22 (1), 55-64. https://doi.org/10.1142/S0129054111007824. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
10_On_a_partial_IJFCS_2201_P55.pdf | 139.9Kb | [PDF] | Ver/ | |