Title of article
On a generalization of extended resolution Original Research Article
Author/Authors
O. Kullmann، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 1999
Pages
28
From page
149
To page
176
Abstract
Motivated by improved SAT algorithms ((O. Kullmann, DIMACS Series, vol. 35, Amer. Math. Soc., Providence, RI, 1997; O. Kullmann, Theoret. Comput. Sci. (1999); O. Kullmann, Inform. Comput., submitted); yielding new worst-case upper bounds) a natural parameterized generalization GER of Extended Resolution (ER) is introduced. ER can simulate polynomially GER, but GER allows special cases for which exponential lower bounds can be proven.
Keywords
Extended resolution , Propositional logic , Lower bounds , Generalized extended resolution , Blocked clauses
Journal title
Discrete Applied Mathematics
Serial Year
1999
Journal title
Discrete Applied Mathematics
Record number
884975
Link To Document