EnglishIn this paper, we introduce general techniques for extending classes of polynomially solvable SAT instances. We generalize the approach of Gallo and Scutellà, obtaining a family of polynomial hierarchies, where one such polynomial hierarchy is a sequence of nested polynomially solvable classes that cover the whole set of CNF formulas. Following a different approach, based on a new decomposition technique, we define the class of Split-Horn formulas, which is a proper extension of the Generalized Horn formulas defined by Yamasaki e Doshita. We discuss and compare the basic properties of the proposed classes; polynomial time recognition and solution algorithms are provided.
Hierarchies of polynomially solvable satisfiability problems / Pretolani, Daniele. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - STAMPA. - 17 (2)(1996), pp. 339-357. [10.1007/BF02127974]
| Data di pubblicazione: | 1996 | |
| Titolo: | Hierarchies of polynomially solvable satisfiability problems | |
| Autore/i: | Pretolani, Daniele | |
| Autore/i UNIMORE: | ||
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/BF02127974 | |
| Rivista: | ||
| Volume: | 17 (2) | |
| Pagina iniziale: | 339 | |
| Pagina finale: | 357 | |
| Codice identificativo ISI: | WOS:A1996VV96100008 | |
| Codice identificativo Scopus: | 2-s2.0-21444456926 | |
| Citazione: | Hierarchies of polynomially solvable satisfiability problems / Pretolani, Daniele. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - STAMPA. - 17 (2)(1996), pp. 339-357. [10.1007/BF02127974] | |
| Tipologia | Articolo su rivista |
File in questo prodotto:
Pubblicazioni consigliate
http://hdl.handle.net/11380/585404
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
Copyright © 2021