New methods for 3-SAT decision and worst-case analysis
We prove the worst-case upper bound 1.5045..(n) for the time complexity of 3-SAT decision, where n is the number of variables in the input formula, introducing new methods for the analysis as well as new algorithmic techniques. We add new 2- and 3-clauses, called "blocked clauses", generalizing the extension rule of "Extended Resolution." Our methods for estimating the size of trees lead to a refined measure of formula complexity of 3-clause-sets and can be applied also to arbitrary trees. (C) 1999 Elsevier Science B.V. All rights reserved.
3-sat worst-case upper bounds blocked clauses extended resolution analysis of algorithms generalized autarkness