|
|
|
|
References
|
|
| |
| 1. |
E. Ya. Dantsin, “Two tautologihood proof systems based on the split method”, Zap. Nauchn. Sem. LOMI, 105, 1981, 24–44    |
| 2. |
A. Golovnev, A. S. Kulikov, A. V. Smal, S. Tamaki, “Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework”, Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs, 58, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016, 45:1–45:16 |
| 3. |
E. A. Hirsch, “New worst-case upper bounds for SAT”, J. Automated Reasoning, 24:4 (2000), 397–420  |
| 4. |
O. Kullmann, “New methods for 3-SAT decision and worst-case analysis”, Theor. Computer Sci., 223:1–2 (1999), 1–72 |
| 5. |
O. Kullmann, H. Luckhardt, Deciding propositional tautologies: Algorithms and their complexity, Technical report, Fachbereich Mathematik, Johann Wolfgang Goethe Universität, 1997 |
| 6. |
B. Monien, E. Speckenmeyer, $3$-satisfability is testable in $O(1.62^r)$ steps, Bericht Nr. 3/1979, Reihe Theoretische Informatik, Universität-Gesamthochschule-Paderborn, 1979 |
| 7. |
S. Nurk, An ${O}(2^{.4058m})$ upper bound for Circuit SAT, PDMI Preprint, 2009 |
| 8. |
R. Paturi, P. Pudlák, M. E. Saks, F. Zane, “An improved exponential-time algorithm for k-SAT”, J. ACM, 52:3 (2005), 337–364 |
| 9. |
R. Santhanam, “Fighting perebor: New and improved algorithms for formula and QBF satisfiability”, Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, 183–192 |
| 10. |
S. V. Savinov, Upper bound for Circuit SAT, MSc Thesis, St. Petersburg Academic University RAS, 2014 |
| 11. |
K. Seto, S. Tamaki, “A satisfiability algorithm and average-case hardness for formulas over the full binary basis”, Comput. Complexity, 22:2 (2013), 245–274 |
| 12. |
L. G. Valiant, V. V. Vazirani, “NP is as easy as detecting unique solutions”, Theor. Computer Sci., 47 (1986), 85–93 |
| 13. |
M. Wahlström, “An algorithm for the SAT problem for formulae of linear length”, Proceedings of the 13th Annual European Symposium on Algorithms, ESA 2005, Lecture Notes in Computer Science, 3669, 2005, 107–118 |
