Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.1 b) and proof of Theorem 7.2, p. 33 — 3-Occurrence Max3Sat L-reduces to R | rⱼ | Σ Cⱼ with α = 32, β = 1

Proved
SkutellaCQP.MaxSNP.l_reduction

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-hardnessl-reductionmax-3-satp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1release-datesschedulingtotal-completion-timeunrelated-machines

Let III be an instance of 3-OCCURRENCE MAX3SAT with nnn variables and mmm clauses, and let R(I)R(I)R(I) be the instance of R ∣ rj ∣∑CjR\,|\,r_j\,|\sum C_jR∣rj​∣∑Cj​ constructed from it: for each variable a v-job of length 444, released at 000, that may run only on the variable's true or false machine; for each clause a c-job of length 000, released at 333, 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 R(I)R(I)R(I) has an optimal schedule S0S_0S0​, and

  1. OPTSCH(R(I))=VAL(S0)=4n+4m−OPTSAT(I)\mathrm{OPT}_{\mathrm{SCH}}(R(I))=\mathrm{VAL}(S_0)=4n+4m-\mathrm{OPT}_{\mathrm{SAT}}(I)OPTSCH​(R(I))=VAL(S0​)=4n+4m−OPTSAT​(I) (Lemma 7.1 b));
  2. OPTSCH(R(I))≤32 OPTSAT(I)\mathrm{OPT}_{\mathrm{SCH}}(R(I))\le 32\,\mathrm{OPT}_{\mathrm{SAT}}(I)OPTSCH​(R(I))≤32OPTSAT​(I);
  3. for every feasible schedule SSS of R(I)R(I)R(I),
OPTSAT(I)−#(SAT(S)) ≤ VAL(S)−OPTSCH(R(I)).\mathrm{OPT}_{\mathrm{SAT}}(I)-\#(\mathrm{SAT}(S))\ \le\ \mathrm{VAL}(S)-\mathrm{OPT}_{\mathrm{SCH}}(R(I)).OPTSAT​(I)−#(SAT(S)) ≤ VAL(S)−OPTSCH​(R(I)).

Items 2 and 3 are the two conditions of an L-reduction with constants α=32\alpha=32α=32 and β=1\beta=1β=1. With the MaxSNP-hardness of 3-OCCURRENCE MAX3SAT they give the MaxSNP-hardness of R ∣ rj ∣∑CjR\,|\,r_j\,|\sum C_jR∣rj​∣∑Cj​ (Theorem 7.2, due to Hoogeveen, Schuurman and Woeginger 1998).

Formalization Note MaxSNP-hardness, polynomial-time computability of RRR and of SAT\mathrm{SAT}SAT, 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. OPTSCH\mathrm{OPT}_{\mathrm{SCH}}OPTSCH​ is not a primitive: the theorem asserts a feasible schedule S0S_0S0​ that is no worse than every feasible schedule. The validity hypothesis on III includes two conventions not written on the page (clauses have one to three literals; every variable occurs); without the second, the constant 323232 fails, since a variable that occurs nowhere adds 444 to OPTSCH\mathrm{OPT}_{\mathrm{SCH}}OPTSCH​ and nothing to OPTSAT\mathrm{OPT}_{\mathrm{SAT}}OPTSAT​.

Preamble
import Mathlib
import Definitions.Def_SkutellaCQP_MaxSNP_Setting
Formal statement
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
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 33, Lemma 7.1 b) and proof of Theorem 7.2
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me