The SAT01 framework for NP problems
Stanislav Busygin · 2007
We consider an NP-complete problem SAT01 having a range of remarkable properties. First, it is equivalent to the weighted independent set problem on a graph Γ with vertex weights w, where the required independent set weight equals the maximum possible κ(Γ, w) value m, and hence is decidable by computation of the weighted Lovász number unless α(Γ, w) < ϑ(Γ, w) = κ(Γ, w) = m. Second, it admits a suitable constraint propagation technique able to simplify many SAT01 instances. Third, a multitude of NP problems reduce to SAT01 in a natural way, without excessive dimensionality growth. At that, the obtained SAT01 formulation tends to have a clear interpretation within notion of the original problem. Finally, we outline a rationale for choosing SAT01 as the framework for NP problems from an information theory viewpoint.