Partial Satisfaction of k-Satisfiable Formulas

A CNF formula is called k-satisfiable if every subformula containing at most k clauses is satisfiable. Let s k be the largest ratio s such that for any k-satisfiable formula F, there is an assignment satisfying at least s | F | clauses. We denote the analogous ratio for formulas with weighted clauses by r k . The numbers r k have already been studied, but little has been known about s k . We show that s k and r k differ for k = 2 , 3 . For k = 2 , we show that s 2 = 2 3 , which is larger than r 2 = ( 5 − 1 ) / 2 ≈ 0.619 , the inverse of the golden ratio. Further, we show that r 3 = 2 3 < 21 / 31 ⩽ s 3 ⩽ 7 / 10 .