A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT

Authors Victor Lagerkvist, Biman Roy



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.64.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Victor Lagerkvist
Biman Roy

Cite AsGet BibTex

Victor Lagerkvist and Biman Roy. A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.64

Abstract

The parameterized satisfiability problem over a set of Boolean relations Gamma (SAT(Gamma)) is the problem of determining whether a conjunctive formula over Gamma has at least one model. Due to Schaefer's dichotomy theorem the computational complexity of SAT(Gamma), modulo polynomial-time reductions, has been completely determined: SAT(Gamma) is always either tractable or NP-complete. More recently, the problem of studying the relationship between the complexity of the NP-complete cases of SAT(Gamma) with restricted notions of reductions has attracted attention. For example, Impagliazzo et al. studied the complexity of k-SAT and proved that the worst-case time complexity increases infinitely often for larger values of k, unless 3-SAT is solvable in subexponential time. In a similar line of research Jonsson et al. studied the complexity of SAT(Gamma) with algebraic tools borrowed from clone theory and proved that there exists an NP-complete problem SAT(R^{neq,neq,neq,01}_{1/3}) such that there cannot exist any NP-complete SAT(Gamma) problem with strictly lower worst-case time complexity: the easiest NP-complete SAT(Gamma) problem. In this paper we are interested in classifying the NP-complete SAT(Gamma) problems whose worst-case time complexity is lower than 1-in-3-SAT but higher than the easiest problem SAT(R^{neq,neq,neq,01}_{1/3}). Recently it was conjectured that there only exists three satisfiability problems of this form. We prove that this conjecture does not hold and that there is an infinite number of such SAT(Gamma) problems. In the process we determine several algebraic properties of 1-in-3-SAT and related problems, which could be of independent interest for constructing exponential-time algorithms.
Keywords
  • clone theory
  • universal algebra
  • satisfiability problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. V. B. Alekseev and A. A. Voronenko. On some closed classes in partial two-valued logic. Discrete Mathematics and Applications, 4(5):401-419, 1994. URL: http://dx.doi.org/10.1515/dma.1994.4.5.401.
  2. L. Barto. Constraint satisfaction problem and universal algebra. ACM SIGLOG News, 1(2):14-24, October 2014. Google Scholar
  3. M. Behrisch, M. Hermann, S. Mengel, and G. Salzer. Give me another one! In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC-2015), pages 664-676, 2015. Google Scholar
  4. M. Behrisch, M. Hermann, S. Mengel, and G. Salzer. As close as it gets. In Proceedings of the 10th International Workshop on Algorithms and Computation (WALCOM-2016), pages 222-235, 2016. Google Scholar
  5. V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras. I. Cybernetics, 5:243-252, 1969. Google Scholar
  6. V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras. II. Cybernetics, 5:531-539, 1969. Google Scholar
  7. F. Börner, L. Haddad, and R. Pöschel. Minimal partial clones. Bull. Austral. Math. Soc., 44:405-415, 1991. Google Scholar
  8. A. Bulatov and A. Hedayaty. Counting problems and clones of functions. Multiple-Valued Logic and Soft Computing, 18(2):117-138, 2012. Google Scholar
  9. D. Geiger. Closed systems of functions and predicates. Pacific Journal of Mathematics, 27(1):95-100, 1968. Google Scholar
  10. L. Haddad and K. Schölzel. Countable intervals of partial clones. In Proceedings of the 44th IEEE International Symposium on Multiple-Valued Logic, (ISMVL-2010), pages 155-160. IEEE Computer Society, 2014. Google Scholar
  11. T. Hertli. 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general. SIAM Journal on Computing, 43(2):718-729, 2014. URL: http://dx.doi.org/10.1137/120868177.
  12. P. Idziak, P. Marković, R. McKenzie, M. Valeriote, and R. Willard. Tractability and learnability arising from algebras with few subpowers. SIAM Journal on Computing, 39(7):3023-3037, June 2010. Google Scholar
  13. R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  14. P. Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200:185-204, 1998. Google Scholar
  15. P. Jonsson, V. Lagerkvist, G. Nordh, and B. Zanuttini. Complexity of SAT problems, clone theory and the exponential time hypothesis. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013), pages 1264-1277, 2013. URL: http://knowledgecenter.siam.org/0236-000094/.
  16. P. Jonsson, V. Lagerkvist, J. Schmidt, and H. Uppman. Relating the time complexity of optimization problems in light of the exponential-time hypothesis. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-14), pages 408-419, Berlin, Heidelberg, 2014. Springer-Verlag. Google Scholar
  17. D. Kavvadias and M. Sideri. The inverse satisfiability problem. SIAM Journal on Computing, 28:152-163, 1998. Google Scholar
  18. V. Lagerkvist. Weak bases of Boolean co-clones. Information Processing Letters, 114(9):462-468, 2014. Google Scholar
  19. V. Lagerkvist. Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I, chapter Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem, pages 357-368. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015. Google Scholar
  20. V. Lagerkvist. Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and Applications. PhD thesis, Linköping University, The Institute of Technology, 2016. Google Scholar
  21. V. Lagerkvist and M. Wahlström. The power of primitive positive definitions with polynomially many variables. To appear in Journal of Logic and Computation, 2016. Google Scholar
  22. V. Lagerkvist, M. Wahlström, and B. Zanuttini. Bounded bases of strong partial clones. In Proceedings of the 45th International Symposium on Multiple-Valued Logic (ISMVL-2015), pages 189-194, 2015. Google Scholar
  23. D. Lau. Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory (Springer Monographs in Mathematics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. Google Scholar
  24. B.A. Romov. The algebras of partial functions and their invariants. Cybernetics, 17(2):157-167, 1981. Google Scholar
  25. T. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory Of Computing (STOC-78), pages 216-226. ACM Press, 1978. Google Scholar
  26. H. Schnoor and I. Schnoor. Partial polymorphisms and constraint satisfaction problems. In N. Creignou, P. G. Kolaitis, and H. Vollmer, editors, Complexity of Constraints, volume 5250 of Lecture Notes in Computer Science, pages 229-254. Springer Berlin Heidelberg, 2008. Google Scholar
  27. I. Schnoor. The weak base method for constraint satisfaction. PhD thesis, Gottfried Wilhelm Leibniz Universität, Hannover, Germany, 2008. URL: http://edok01.tib.uni-hannover.de/edoks/e01dh08/559615132.pdf.
  28. K. Schölzel. Clones of partial functions on finite sets. PhD thesis, Universität Rostock, 2010. Google Scholar
  29. K. Schölzel. Dichotomy on intervals of strong partial boolean clones. Algebra Universalis, 73(3-4):347-368, 2015. Google Scholar
  30. M. Wahlström. Algorithms, measures and upper bounds for satisfiability and related problems. PhD thesis, Linköping University, TCSLAB - Theoretical Computer Science Laboratory, The Institute of Technology, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail