Proof of Thm 4, p. 21 — arithmetization: [y ∨ z] = 3/4 − y/4 − z/4 − yz/4 on {−1,1}², so OBJ = Σ_C w_C(3/4 − y/4 − z/4 − yz/4)
ProvedOptInapprox.Bal2Sat.clause_aritharithmetizationmax-2satp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Treat TRUE as and FALSE as . For , the truth value of the clause (which is exactly when or ) is the polynomial
Consequently, for every weighted MAX-2SAT instance and every assignment , writing each clause as with , ,
This turns the combinatorial objective into a quadratic polynomial in the variables, the starting point of the semidefinite relaxation.
Formalization Note The first conjunct is the pointwise identity on ; the second expresses the satisfied weight (defined via Boolean literal truth) through the literal values litVal.
Preamble
import Mathlib import Definitions.Def_OptInapprox_Bal2Sat_Setting
Formal statement
namespace OptInapprox.Bal2Sat
/-- Clause arithmetization, proof of Theorem 4, p. 21: with TRUE = −1, a clause `(y ∨ z)` with
`y, z ∈ {−1, 1}` is satisfied (value 1) iff `y = −1` or `z = −1`, and this indicator equals
`3/4 − y/4 − z/4 − yz/4`. Hence the weighted MAX-2SAT objective is
`OBJ = Σ_{C=(y∨z)} w_C (3/4 − y/4 − z/4 − y·z/4)`. -/
theorem clause_arith :
(∀ y z : ℝ, (y = 1 ∨ y = -1) → (z = 1 ∨ z = -1) →
(if y = -1 ∨ z = -1 then (1 : ℝ) else 0) = 3 / 4 - 1 / 4 * y - 1 / 4 * z - 1 / 4 * (y * z)) ∧
∀ {n : ℕ} (I : Instance n) (x : Fin n → Bool),
satWeight I x = ∑ c, I.w c *
(3 / 4 - 1 / 4 * litVal (I.clause c).1 x - 1 / 4 * litVal (I.clause c).2 x
- 1 / 4 * (litVal (I.clause c).1 x * litVal (I.clause c).2 x)) := by sorry
end OptInapprox.Bal2Sat
Source
Khot, Kindler, Mossel & O'Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM J. Comput. 37(1), 2007 (authors' version of February 7, 2007), p. 21, §9, proof of Theorem 4 (arithmetization and the first display OBJ)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.