New efficient method tests satisfiability of bounded formulas
A One-Sided Sublinear-Query Tester for Bounded-Degree 2SAT
Data Structures and Algorithms
Summary
The paper deals with checking if certain logical statements called 2CNF formulas can be true or are satisfiable. It focuses on formulas where each variable appears only a limited number of times, known as bounded-degree formulas. The authors present a method that tests these formulas quickly by looking at just a small part of them, rather than the whole. This approach guarantees it won’t incorrectly claim a satisfiable formula is unsatisfiable.
What this means in practice
- •For software verification teams: Speed up checks for logical constraint consistency in programs with limited variable interactions.
- •For automated reasoning engineers: Reduce query complexity when testing satisfiability in optimization problems with bounded-degree constraints.
A theory result. No direct application yet.
Authors
Yuichi Yoshida
Abstract
We give a one-sided tester for satisfiability of 2CNF formulas in the bounded-degree model. For every degree bound $Δ$, distance parameter $\varepsilon>0$, and $ν\in(0,1/2)$, its query complexity on $n$-variable formulas is $\widetilde O_{\varepsilon,Δ,ν}(n^{1/2+ν})$.