TL;DR
This paper introduces and analyzes the complexity of DISTANCE-SAT, a problem that asks whether a propositional formula has a model disagreeing with a given partial configuration by at most d variables. They propose two algorithms, DPdistance and DPdistance+lasso, and empirically show that DPdistance+lasso, which uses a novel "lasso" branching strategy, often significantly outperforms the standard DPdistance, especially for difficult instances.
What Problem Does This Paper Address?
In many AI applications, we need to find solutions that are not just valid but also "close" to a desired or expected state. Imagine diagnosing a faulty machine: you have a model of how it should work (the expected configuration), and you observe it's not working. You need to find the minimal set of component failures (deviations from the expected state) that explains the observed behavior. This "closeness" problem is prevalent in areas like diagnosis, belief revision, and constraint satisfaction.
This paper formalizes this "closeness" problem in propositional logic. Given a knowledge base (a CNF formula $\Sigma$), an expected configuration (a partial interpretation $PI$), and a maximum allowed disagreement $d$, the DISTANCE-SAT problem asks: "Does there exist a model of $\Sigma$ that differs from $PI$ on at most $d$ variables?" This is a natural extension of the standard SAT problem, where $d$ is effectively infinite (or the number of variables).
Methods
The authors tackle DISTANCE-SAT using two main approaches, both building upon the well-established Davis-Putnam (DP) search procedure for SAT:
- DPdistance: This is a straightforward adaptation of the standard DP algorithm. It maintains a counter at each node of the search tree that tracks the number of variables on which the current partial assignment disagrees with the target partial interpretation $PI$. If this counter exceeds $d$, the algorithm backtracks. The branching rule used is a standard, efficient heuristic for SAT.
- DPdistance+lasso: This is a more aggressive variant. Its key innovation lies in its branching rule. Instead of considering all variables, it prioritizes variables that appear in clauses that are completely falsified by the target partial interpretation $PI$. Among these "critical" clauses, it selects those of minimal length. Then, from the variables within these clauses, it picks one that maximizes a standard SAT branching heuristic. This "lasso" effect aims to quickly satisfy the distance constraint.
Datasets
The authors evaluate their algorithms on randomly generated 3-CNF instances. These instances are generated using the "fixed-length clauses model" (Chvátal & Szemerédi 1988), where clauses have a fixed length (3 in this case) and variables are drawn uniformly. They explore various parameters:
- Number of variables (up to 100).
- Number of clauses.
- Size of the reference partial interpretation ($PI$).
- The maximum allowed distance $d$.
No new benchmark datasets are introduced; rather, they use a standard random instance generation method to test the algorithms across a range of problem characteristics.
Key Insights and Ideas
- DISTANCE-SAT is NP-complete: Like SAT, DISTANCE-SAT is computationally hard in the general case. However, its complexity doesn't significantly increase beyond SAT's.
- Tractable SAT fragments don't guarantee tractable DISTANCE-SAT: Even when the knowledge base $\Sigma$ is restricted to tractable forms (like Horn or Krom clauses), DISTANCE-SAT remains NP-hard unless the distance bound $d$ is fixed. This suggests that the distance constraint adds significant complexity.
- The "Lasso Effect": The DPdistance+lasso algorithm's novel branching strategy can lead to a "lasso effect" when the reference interpretation $PI$ is complete. In this scenario, the algorithm can run in polynomial time ($O(|\Sigma| \cdot k^d)$ where $k$ is the maximum clause length), which is a significant theoretical advantage.
- Difficulty Peaks Near Transition: The most difficult DISTANCE-SAT instances tend to occur near the "satisfiability threshold," where the problem transitions from being mostly satisfiable to mostly unsatisfiable. These instances are often harder than their SAT counterparts (where the distance constraint is ignored).
- Partial Interpretations are Challenging: While the lasso effect is guaranteed for complete $PI$, the DPdistance+lasso algorithm still shows significant performance gains over DPdistance even with partial $PI$, indicating its practical utility.
Key Results
- DPdistance+lasso outperforms DPdistance: For many difficult instances (especially those with smaller $d$ and fewer clauses), DPdistance+lasso requires significantly fewer variable assignments (i.e., is faster) than DPdistance. Figure 3 shows ratios where DPdistance+lasso can be orders of magnitude faster.
- DPdistance is better for large $d$: Conversely, when $d$ is large, the standard DPdistance algorithm sometimes performs better, suggesting that the aggressive heuristic of DPdistance+lasso might be less effective when the distance constraint is not very restrictive.
- Instance difficulty: DISTANCE-SAT instances, particularly those with partial reference interpretations, can be significantly harder than equivalent SAT instances. Figure 7 shows that DPdistance+lasso can push back the intractability for these difficult cases.
- Impact of $d$ and $|Dom(PI)|$: Figure 1 and 4 illustrate how the proportion of satisfiable instances changes dramatically with $d$ and the size of the domain of $PI$. Smaller $d$ and larger $|Dom(PI)|$ generally lead to fewer satisfiable instances.
Limitations and Future Work
- Limitations: The paper focuses on propositional logic. Extending these concepts to first-order logic or other formalisms would be a natural next step. The empirical evaluation is primarily on random 3-CNF instances; performance on structured, real-world problems might differ.
- Future Work: The authors suggest extending their algorithms to handle multiple distance constraints simultaneously. They also note that their algorithms can be easily adapted to solve the "function problem" (i.e., finding a model that satisfies the distance constraint, not just deciding if one exists). Encoding DISTANCE-SAT instances as propositional cardinality formulas is also mentioned as an interesting connection for further research.
Summary updated