Artículo
Cooperative P Systems and the P Versus NP Problem
Autor/es | Valencia Cabrera, Luis
Martínez del Amor, Miguel Ángel Orellana Martín, David Pérez Hurtado de Mendoza, Ignacio 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 | 2021-11-25 |
Publicado en |
|
Resumen | The P versus NP problem is undoubtedly the most important open question
in computer science. Frontiers of tractability or efficiency expressed by means of syntactic
or semantic ingredients in the framework of Membrane ... The P versus NP problem is undoubtedly the most important open question in computer science. Frontiers of tractability or efficiency expressed by means of syntactic or semantic ingredients in the framework of Membrane Computing, an unconventional computing paradigm, can bring a new approach to tackle P versus NP. In this context, the role of the cooperation of objects to trigger rewriting rules is analysed in order to obtain this kind of borderlines. Besides, a relationship among cooperative rewriting rules and instances of 2–SAT problem and 3–SAT problem is highlighted and their connections with results of computational complexity theory are described |
Cita | Valencia Cabrera, L., Martínez del Amor, M.Á., Orellana Martín, D., Pérez Hurtado de Mendoza, I. y Pérez Jiménez, M.d.J. (2017). Cooperative P Systems and the P Versus NP Problem. The Bulletin of International Membrane Computing Society, 4 (December 2017), 39-64. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
BullDec2017.pdf | 8.321Mb | [PDF] | Ver/ | |