I am doing a survey on k-SAT where time complexity is in terms of n, i.e. the number of variables in a formula. As for the fast algorithms for k-SAT, we see biased-PPSZ, PPSZ, Schöning's local search, algorithms which combine PPSZ and Schöning's local search, algorithms which derandomize PPSZ or Schöning's local search.
There are many papers which are discussing improvement and property of PPSZ. However, where are other deterministic algorithms going? Is there no future for every deterministic algorithm which is not a derandomization of PPSZ or Schöning's local search or their improvement,combination?
There exists deterministic fast branching algorithms which are not derandomization from some randomized algorthms for k-SAT where time complexity is in terms of m and l, i.e. the number of clauses in a formula and the length of a formula. And there is a branching algorithm, and in the early papers which discuss k-SAT in terms of n, there is also algorithm using branching algorithm to obtain a speed which is from Burkhard Monien and Ewald Speckenmeyer. For 2-SAT, there is linear time deterministic algorithm based on strongly connected components of a contructed graph.
After Hertli reveals that unique-SAT bounds for PPSZ hold in general, work turns from derandomizing and improving Schöning's local search to derandomize PPSZ and improve that. Are there any possibilities for those deterministic algorithms without derandomization like some branching algorithms? What if some techniques like measure and conquer are contributed to k-SAT? No matter how, it must be admitted that PPSZ and Schöning's local search are both simple and efficient.
Papers I mention are as follows.
- schöning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction k Problems
- Evgeny Dantsin, Andreas Goerdt, Edward A Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, and Uwe Sch¨oning. A deterministic (2-2/(k+1))n algorithm for k-sat based on local search. Theoretical Computer Science, 289(1):69–83, 2002.
- S. Cliff Liu, Simpler Partial Derandomization of PPSZ for k-SAT
- Daniel Rolf. Derandomization of PPSZ for unique- k-sat. In 8th International Conference on Theory and Applications ofSatisfiability Testing, SAT 2005, pages 216–225, 2005.
- S. Cliff Liu, Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT∗
- Robin A. Moser and Dominik Scheder, A full derandomization of schöning’s k-sat algorithm. In 43rd Annual ACMSymposium on Theory ofComputing, STOC 2011, pages 245–252, 2011.
- Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- Dominik Scheder and John P. Steinberger, PPSZ for General k-SAT – Making Hertli’s Analysis Simpler and 3-SAT Faster∗
- Pavel Pudlák, Dominik Scheder, and Navid Talebanfard, Tighter Hard Instances for PPSZ
- Burkhard Monien and Ewald Speckenmeyer. 1985. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10, 3 (1985), 287–295.
- Jianer Chen and Yang Liu, An Improved SAT Algorithm in Terms of Formula Length
- Bengt ASPVALL, Michael F. PLASS and Robert Endre TARJAN, A LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS
- Timon Hertli. 2014. Breaking the PPSZ Barrier for Unique 3-SAT. In Proc. of41st ICALP I. 600–611.
- Ramamohan Paturi, Pavel Pudlák, and Francis Zane. 1999. Satisfiability Coding Lemma. Chicago J. Theor. Comput. Sci. (1999).
- Tong Qin and Osamu Watanabe. 2018. An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. In International Workshop on Algorithms and Computation. Springer, 93–105.
- Thomas Hofmeister, Uwe Sch¨oning, Rainer Schuler, and Osamu Watanabe. A probabilistic 3sat algorithm further improved. In 19th Annual Symposium on Theoretical Aspects ofComputer Science, STACS 2002, pages 192–202. Springer, 2002.
- Improving PPSZ for 3-SAT using Critical Variables