On the Satisfaction Probability of k-CNF Formulas
share
The satisfaction probability σ(ϕ) := _β:vars(ϕ) →{0,1}[βϕ] of a propositional formula ϕ is the likelihood that a random assignment β makes the formula true. We study the complexity of the problem ksat-prob_>δ = {ϕ is a kcnf formula |σ(ϕ) > δ} for fixed k and δ. While 3sat-prob_>0 = 3sat is NP-complete and sat-prob_>1/2 is PP-complete, Akmal and Williams recently showed 3sat-prob_>1/2∈ P and 4sat-prob_>1/2∈ NP-complete; but the methods used to prove these striking results stay silent about, say, 4sat-prob_>3/4, leaving the computational complexity of ksat-prob_>δ open for most k and δ. In the present paper we give a complete characterization in the form of a trichotomy: ksat-prob_>δ lies in AC^0, is NL-complete, or is NP-complete; and given k and δ we can decide which of the three applies. The proof of the trichotomy hinges on a new order-theoretic insight: Every set of kcnf formulas contains a formula of maximum satisfaction probability. This deceptively simple result allows us to (1) kernelize ksat-prob_≥δ, (2) show that the variables of the kernel form a strong backdoor set when the trichotomy states membership in AC^0 or NL, and (3) prove a new locality property for the models of second-order formulas that describe problems like ksat-prob_≥δ. The locality property will allow us to prove a conjecture of Akmal and Williams: The majority-of-majority satisfaction problem for kcnfs lies in P for all k.
READ FULL TEXT