| Articolul precedent |
| Articolul urmator |
 |
 316 4 |
| Ultima descărcare din IBN: 2023-12-04 16:09 |
 SM ISO690:2012DIAZ-PERNIL, Daniel, ALHAZOV, Artiom, FREUND, Rudolf. Solving SAT with Antimatter in Membrane Computing. In: Brainstorming Week On Membrane Computing, 2-6 februarie 2015, Sevilla. Sevilla, Spania: Fénix Editora, 2015, Ediția a 13-a, pp. 121-130. ISBN 978-84-84-944366-2-8. |
| EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
| Brainstorming Week On Membrane Computing Ediția a 13-a, 2015 |
||||||
|
Masa rotundă "13th Brainstorming Week on Membrane Computing" Sevilla, Spania, 2-6 februarie 2015 | ||||||
|
||||||
| Pag. 121-130 | ||||||
|
||||||
 Descarcă PDF |
||||||
| Rezumat | ||||||
The set of NP-complete problems is split into weakly and strongly NPcomplete 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. |
||||||
|
|
|
|
