RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI

Zap. Nauchn. Sem. POMI, 2002, Volume 293, Pages 118–128 (Mi znsl1678)

An upper bound $O(2^{0.16254n})$ for Exact 3-Satisfiability: a simpler proof
A. S. Kulikov

This publication is cited in the following articles:
  1. Mandra S., Guerreschi G.G., Aspuru-Guzik A., “Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems”, New J. Phys., 18 (2016), 073003  crossref  isi  scopus
  2. JUNPING ZHOU, WEIHUA SU, JIANAN WANG, “NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY”, Int. J. Found. Comput. Sci., 25:06 (2014), 667  crossref
  3. Byskov J.M., Madsen B.A., Skjernaa B., “New algorithms for Exact Satisfiability”, Theoret. Comput. Sci., 332:1-3 (2005), 515–541  crossref  mathscinet  zmath  isi  scopus
  4. Kneis J., Molle D., Richter S., Rossmanith P., “On the Parameterized Complexity of Exact Satisfiability Problems”, Mathematical Foundations of Computer Science 2005, Proceedings, Lecture Notes in Computer Science, 3618, eds. Jedrzejowicz J., Szepietowski A., Springer-Verlag Berlin, 2005, 568–579  crossref  mathscinet  zmath  isi
  5. A. S. Kulikov, S. S. Fedin, “Automated proofs of upper bounds on the running time of splitting algorithms”, J. Math. Sci. (N. Y.), 134:5 (2006), 2383–2391  mathnet  crossref  mathscinet  zmath
  6. Dahllöf V., Jonsson P., Beigel R., “Algorithms for four variants of the exact satisfiability problem”, Theoret. Comput. Sci., 320:2-3 (2004), 373–394  crossref  mathscinet  zmath  isi  scopus
  7. Gramm J., Guo J., Huffner F., Niedermeier R., “Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems”, Algorithmica, 39:4 (2004), 321–347  crossref  mathscinet  zmath  isi  scopus
  8. Fedin S., Kulikov A., “Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms”, Parameterized and Exact Computation, Proceedings, Lecture Notes in Computer Science, 3162, eds. Downey R., Fellows M., Dehne F., Springer-Verlag Berlin, 2004, 248–259  crossref  zmath  isi


© Steklov Math. Inst. of RAS, 2026