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

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+ν})$.