SAT Lecture Notes "Boolean Satisfiability - Combinatorics and Algorithms"- Updates

• The currently best known bound for a deterministic 3-SAT algorithm is O(1.473ⁿ), see [Brueggemann, Kern, 2004] (improvement on previous bound of O(1.481ⁿ) in [Dantsin etal, 2002]).
  [Brueggemann, Kern, 2004] Tobias Brueggemann, Walter Kern, An improved local search algorithm for 3-SAT, Theoretical Computer Science 329:1-3 (2004) 303-313. pdf


• There are two new papers concerning the problem on k-satisfiable CNF formulas. Among others, [Král', 2003] proves the a tight ratio of always satisfiable clauses for a 4-satisfiable CNF formula (of roughly 0.6992).
  [Král', 2003] Daniel Král', Locally satisfiable formulas, Proceedings of the 15th annual ACM-SIAM symposium on Discrete algorithms (SODA) (2004) 330-339. ps
  [Trevisan, 2004] Luca Trevisan, On Local Versus Global Satisfiability, SIAM Journal on Discrete Mathematics, 17:4 (2004)541-547. ps
  See also Section 20.6 in
  [Jukna, 2001] Satasys Jukna, Extremal Combinatorics - With Applications in Computer Science, Springer Verlag Berlin Heidelberg (2001).