Partial Satisfaction of k-Satisfiable Formulas

A CNF formula is called k-satisfiable if every subformula containing at most k clauses is satisfiable. Let sk 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 rk. The numbers rk have already been studied, but little has been known about sk. We show that sk and rk differ for k=2,3. For k=2, we show that , which is larger than , the inverse of the golden ratio. Further, we show that .