In 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]

Hierarchies of polynomially solvable satisfiability problems

PRETOLANI, Daniele
1996

Abstract

In 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.
17 (2)
339
357
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]
Pretolani, Daniele
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/585404
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 8
social impact