Presentation
Solving SAT with Antimatter in Membrane Computing
Author/s | Díaz Pernil, Daniel
Alhazov, Artiom Freund, Rudolf Gutiérrez Naranjo, Miguel Ángel |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2015 |
Deposit Date | 2016-01-21 |
Published in |
|
ISBN/ISSN | 978-84-944366-2-8 |
Abstract | 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. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 |
Files | Size | Format | View | Description |
---|---|---|---|---|
121_bwmc2015antiSATu.pdf | 246.7Kb | [PDF] | View/ | |