Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures

摘要

It is known that random k-Sat instances with at least cn random clauses where c = c_k is a suitable constant are unsatisfiable with high probability. These results are obtained by estimating the expected number of satisfying assignments and thus do not provide us with an efficient algorithm. Concerning efficient algorithms it is only known that formulas with n~ε · n~(k/2) clauses with k literals over n underlying variables can be efficiently certified as unsatisfiable. The present paper is the result of trying to lower the preceding bound. We obtain better bounds for some specialized satisfiability problems.