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.

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021