Say that a k-CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 - 2-k +p 2-k of its clauses (note that every k-CNF formula is 0-satisfiable). Let Fk(n, m) denote a random k-CNF formula on n variables with m clauses. For every k2 and every r>0 we determine p and Δ=Δ(k)=O(k2-k/2) such that with probability tending to 1 as n→, a random k-CNF formula F k(n, rn) is p-satisfiable but not (p+Δ)-satisfiable.
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
- Maximum satisfiability