Ponencia
Solving SAT with Antimatter in Membrane Computing
Autor/es | Díaz Pernil, Daniel
Alhazov, Artiom Freund, Rudolf Gutiérrez Naranjo, Miguel Ángel |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2015 |
Fecha de depósito | 2016-01-21 |
Publicado en |
|
ISBN/ISSN | 978-84-944366-2-8 |
Resumen | The set of NP-complete problems is split into weakly and strongly NP-
complete ones. The di erence consists in the in
uence of the encoding scheme of the
input. In the case of weakly NP-complete problems, the intractability ... The set of NP-complete problems is split into weakly and strongly NP- complete ones. The di erence consists in the in uence of the encoding scheme of the input. In the case of weakly NP-complete problems, the intractability depends on the encoding scheme, whereas in the case of strongly NP-complete problems the problem is intractable even if all data are encoded in a unary way. The reference for strongly NP-complete problems is the Satis ability Problem (the SAT problem). In this paper, we provide a uniform family of P systems with active membranes which solves SAT { without polarizations, without dissolution, with division for elementary membranes and with matter/antimatter annihilation. To the best of our knowledge, it is the rst solution to a strongly NP-complete problem in this P system model. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
121_bwmc2015antiSATu.pdf | 246.7Kb | [PDF] | Ver/ | |