Super solutions of random (3 + p)-SAT

In this paper, we propose a model named random ( 3 + p ) -SAT, where a random formula ϕ = ϕ ( n, r, p ) contains n variables and rn clauses, and ( 1 − p ) r n of the clauses are 3-clauses and prn of the clauses are 4-clauses. This paper studies the ( 1, 0 ) -satisfiability of random ( 3 + p ) -SAT and obtains rigorous results that the exact ( 1, 0 ) -satisfiability threshold is r p ⁎ = 1 / 3 ( 1 − p ) if p ≤ 3 / 7. For p ≥ 3 / 7, we give lower and upper bounds of the ( 1, 0 ) -satisfiability threshold, where the lower bound is obtained by using the Unit-Clause algorithm, and the upper bound is obtained by using a novel way to count precisely the subset of all ( 1, 0 ) -satisfying assignments that satisfy a “locally maximum” condition.

Authors

• Bin Wang Qihoo 360 AI Research
• Guangyan Zhou

Keywords

• ( 1, 0 ) -satisfiable
• Super solution
• Phase transition
• Unit Clause