An apparently innocent problem in Membrane Computing
| Autor: | Orellana Martín, David, Valencia Cabrera, Luis, Riscos Núñez, Agustín, Pérez Jiménez, Mario de Jesús, Research Group on Natural Computing (Coordinador) |
|---|---|
| Přispěvatelé: | Research Group on Natural Computing, Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla. TIC193: Computación Natural |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | idUS. Depósito de Investigación de la Universidad de Sevilla instname |
| Popis: | The search for effcient solutions of computationally hard problems by means of families of membrane systems has lead to a wide and prosperous eld of research. The study of computational complexity theory in Membrane Computing is mainly based on the look for frontiers of effciency between different classes of membrane systems. Every frontier provides a powerful tool for tackling the P versus NP problem in the following way. Given two classes of recognizer membrane systems R1 and R2, being systems from R1 non-effcient (that is, capable of solving only problems from the class P) and systems from R2 presumably e cient (that is, capable of solving NP-complete problems), and R2 the same class that R1 with some ingredients added, passing from R1 to R2 is comparable to passing from the non effciency to the presumed effciency. In order to prove that P = NP, it would be enough to, given a solution of an NP-complete problem by means of a family of recognizer membrane systems from R2, try to remove the added ingredients to R2 from R1. In this paper, we study if it is possible to solve SAT by means of a family of recognizer P systems from AM0(�����d;+n), whose non-effciency was demonstrated already. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|