2026-07-23T19:18:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6806 2024-03-06T10:38:56Z ddc:004 open_access

A Gap Trichotomy for Boolean Constraint Problems: Extending Schaefer's Theorem Ham, Lucy Constraint Satisfaction Problem Robust satisfiability Clone theory Dichotomy Trichotomy Boolean 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lucy Ham 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.36 urn:nbn:de:0030-drops-68060 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.36 eng https://creativecommons.org/licenses/by/3.0/legalcode