Lemma 7.1 b) and proof of Theorem 7.2, p. 33 — 3-Occurrence Max3Sat L-reduces to R | rⱼ | Σ Cⱼ with α = 32, β = 1
ProvedSkutellaCQP.MaxSNP.l_reductionLet be an instance of 3-OCCURRENCE MAX3SAT with variables and clauses, and let be the instance of constructed from it: for each variable a v-job of length , released at , that may run only on the variable's true or false machine; for each clause a c-job of length , released at , that may run on the false machine of each variable occurring nonnegated in the clause and on the true machine of each variable occurring negated. Then has an optimal schedule , and
- (Lemma 7.1 b));
- ;
- for every feasible schedule of ,
Items 2 and 3 are the two conditions of an L-reduction with constants and . With the MaxSNP-hardness of 3-OCCURRENCE MAX3SAT they give the MaxSNP-hardness of (Theorem 7.2, due to Hoogeveen, Schuurman and Woeginger 1998).
Formalization Note MaxSNP-hardness, polynomial-time computability of and of , and the definition of an L-reduction are not formalized; the statement is the mathematical content of the two L-reduction conditions for this particular reduction. is not a primitive: the theorem asserts a feasible schedule that is no worse than every feasible schedule. The validity hypothesis on includes two conventions not written on the page (clauses have one to three literals; every variable occurs); without the second, the constant fails, since a variable that occurs nowhere adds to and nothing to .
import Mathlib import Definitions.Def_SkutellaCQP_MaxSNP_Setting
namespace SkutellaCQP.MaxSNP
/-- Lemma 7.1 b) and the two L-reduction conditions of the proof of Theorem 7.2 (p. 33), with
`α = 32` and `β = 1`: `R(I)` has an optimal schedule `S₀` with
`VAL(S₀) = 4n + 4m − OPT_SAT(I) ≤ 32 · OPT_SAT(I)`, and every feasible schedule `S` satisfies
`OPT_SAT(I) − #(SAT(S)) ≤ VAL(S) − VAL(S₀)`. -/
theorem l_reduction {n m : ℕ} (I : Occ3Max3Sat n m) (hI : I.IsValid) :
∃ S₀ : Sched n m, Feasible I S₀ ∧ VAL S₀ = (4 * n + 4 * m : ℝ) - optSat I ∧
(∀ S, Feasible I S → VAL S₀ ≤ VAL S) ∧ VAL S₀ ≤ 32 * optSat I ∧
∀ S, Feasible I S → (optSat I : ℝ) - satCount I (SAT S) ≤ VAL S - VAL S₀ := by sorry
end SkutellaCQP.MaxSNP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.