Stability conditions separate solvable and hard Boolean constraint problems
Stability Dichotomies for Boolean Constraint Satisfaction Problems
Data Structures and Algorithms
Summary
Boolean constraint satisfaction problems (CSPs) involve finding values for variables that satisfy given rules. The authors study how stable the problem-solving methods are when a rule is removed, measuring this with a concept called average sensitivity. They show a clear split: some problem types allow stable and efficient solving or approximating methods, while others are inherently unstable and difficult on large instances. These splits depend on structural properties of the problem rules, such as whether contradictions can be found in small subsets or by local checks.
What this means in practice
- •For algorithm engineers: Identify whether Boolean CSP instances can be efficiently solved with stable algorithms by checking structural properties of constraints.
- •For optimization software developers: Design approximation algorithms for Boolean CSPs with guaranteed stability if the problem has bounded width.
A theory result. No direct application yet.
Authors
Chunyang Wang, Yuichi Yoshida
Abstract
We study the stability of Boolean constraint satisfaction problems (CSPs) through the notion of average sensitivity (Varma and Yoshida, SODA 2021; SICOMP 2023). It measures the expected $1$-Wasserstein distance between an algorithm's output distributions before and after the deletion of a uniformly chosen constraint, using the unnormalized Hamming metric. We establish two dichotomies for every finite Boolean constraint language $Γ$, where $n\geq 2$ denotes the number of variables in an instance. For stable solvability, exactly one of the following holds: $\bullet$ either there is an algorithm that solves $\mathrm{CSP}(Γ)$ and has average sensitivity $O_Γ(1)$ for all satisfiable instances; $\bullet$ or every algorithm that solves $\mathrm{CSP}(Γ)$ has average sensitivity $Ω_Γ(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $Γ$ has finite duality: unsatisfiability can be witnessed on a bounded number of variables. For stable approximability, where a $(1-\varepsilon)$-approximation violates at most an $\varepsilon$-fraction of the constraints in expectation, exactly one of the following holds: $\bullet$ either for every $\varepsilon\in(0,1]$, there is an algorithm that $(1-\varepsilon)$-approximates $\mathrm{CSP}(Γ)$ with average sensitivity $O_Γ(\varepsilon^{-1}\log n)$ for all satisfiable instances; $\bullet$ or there exists $\varepsilon_Γ\in(0,1]$ such that every algorithm that $(1-\varepsilon_Γ)$-approximates $\mathrm{CSP}(Γ)$ has average sensitivity $Ω_Γ(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $Γ$ has bounded width: local consistency checks on bounded sets of variables detect unsatisfiability.