Presentation
An optimal solution to the SAT problem with tissue P systems
Author/s | Orellana Martín, David
Valencia Cabrera, Luis Pérez Jiménez, Mario de Jesús |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2020 |
Deposit Date | 2021-01-22 |
Published in |
|
Abstract | In the framework of membrane computing, several frontiers of e ciency have
been found with respect to the resources that di erent families of P systems take to solve
a decision problem. Each of these frontiers provides ... In the framework of membrane computing, several frontiers of e ciency have been found with respect to the resources that di erent families of P systems take to solve a decision problem. Each of these frontiers provides a new way to tackle the P versus NP problem. In this sense, optimal frontiers are needed in order to separate close variants of P systems. In a previous work, an e cient solution to SAT was given in the framework of P systems from T DC(3). In this work, we will provide an optimal solution to the SAT problem in terms of length of the rules. |
Funding agencies | Ministerio de Economia, Industria y Competitividad (MINECO). España |
Project ID. | TIN2017-89842-P (MABICAP) |
Citation | Orellana Martín, D., Valencia Cabrera, L. y Pérez Jiménez, M.d.J. (2020). An optimal solution to the SAT problem with tissue P systems. En BWMC 2020: Eighteenth Brainstorming Week on Membrane Computing (91-100), Sevilla, España: Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
091_sattissue.pdf | 263.0Kb | [PDF] | View/ | |