Document Open Access Logo

A Gap Trichotomy for Boolean Constraint Problems: Extending Schaefer's Theorem

Author Lucy Ham

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2016.36.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Constraint Satisfaction Problem
  • Robust satisfiability
  • Clone theory
  • Dichotomy
  • Trichotomy
  • Boolean

Metrics

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

Abstract

In this paper, we investigate "gap problems", which are promise problems where YES instances are flexibly satisfiable in a certain sense, and NO instances are not satisfiable at all. These gap problems generalise a family of constraint-related decision problems, including the constraint satisfaction problem itself, the separation problem (can distinct variables be validly assigned distinct values?) and the 2-robust satisfiability problem (does any assignment on two variables extend to a full satisfying assignment?). We establish a Gap Trichotomy Theorem, which on Boolean domains, completely classifies the complexity of the gap problems considered. As a consequence, we obtain several well-known dichotomy results, as well as dichotomies for the separation problem and the 2-robust satisfiability problem: all are either polynomial-time tractable or NP-complete. Schaefer’s original dichotomy is a notable particular case.

Cite As Get BibTex

Lucy Ham. A Gap Trichotomy for Boolean Constraint Problems: Extending Schaefer's Theorem. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.36

Author Details

Lucy Ham

References

  1. Samson Abramsky, Georg Gottlob, and Phokion G. Kolaitis. Robust constraint satisfaction and local hidden variables in quantum mechanics. In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, 2013. Google Scholar
  2. Libor Barto and Marcin Kozik. Robust satisfiability of constraint satisfaction problems. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012, pages 931-940, 2012. Google Scholar
  3. Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM, 61(1):3:1-3:19, 2014. Google Scholar
  4. Libor Barto, Marcin Kozik, and Todd Niven. The CSP dichotomy holds for digraphs with no sources and no sinks (A positive answer to a conjecture of bang-jensen and hell). SIAM J. Comput., 38(5):1782-1802, 2009. Google Scholar
  5. Adam Beacham and Joseph C. Culberson. On the complexity of unfrozen problems. Discrete Applied Mathematics, 153(1-3):3-24, 2005. Google Scholar
  6. Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, 2005. Google Scholar
  7. Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, January 2006. Google Scholar
  8. Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Logic, 12(4):24:1-24:66, July 2011. Google Scholar
  9. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34, 2013. Google Scholar
  10. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  11. David Geiger. Closed systems of functions and predicates. Pacific J. Math., 27:95-100, 1968. Google Scholar
  12. Oded Goldreich. On promise problems: A survey. In Theoretical Computer Science, Essays in Memory of Shimon Even, pages 254-290, 2006. Google Scholar
  13. M. Jackson. Flexible constraint satisfiability and a problem in semigroup theory. ArXiv e-prints, 2015. URL: http://arxiv.org/abs/1512.03127.
  14. Peter Jeavons. On the algebraic structure of combinatorial problems. Theor. Comput. Sci., 200(1-2):185-204, 1998. Google Scholar
  15. Peter Jeavons, David A. Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997. Google Scholar
  16. Benoit Larose and Pascal Tesson. Universal algebra and hardness results for constraint satisfaction problems. Theor. Comput. Sci., 410(18):1629-1647, 2009. Google Scholar
  17. R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic phase transitions. Nature, 400:133-137, 1998. Google Scholar
  18. E. L. Post. The two-valued iterative systems of mathematical logic, volume no. 5 of Annals of Mathematics studies. Princeton University Press, Princeton, 1941. Google Scholar
  19. B. A. Romov. The algebras of partial functions and their invariants. Cybernetics, 17:157-167, 1981. Google Scholar
  20. Thomas J. Schaefer. The complexity of satisfiability problems. In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216-226. ACM, 1978. Google Scholar
  21. Henning Schnoor and Ilka Schnoor. Partial polymorphisms and constraint satisfaction problems. In Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar]., pages 229-254, 2008. Google Scholar
  22. Ilka Schnoor. The weak base method for constraint satisfaction. PhD thesis, University of Hanover, 2008. Google Scholar
  23. Edward P. K. Tsang. Foundations of constraint satisfaction. Computation in cognitive science. Academic Press, 1993. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact