Lemma 7.1 a), p. 32 — every feasible schedule S of R(I) has #(SAT(S)) ≥ 4n + 4m − VAL(S)
ProvedSkutellaCQP.MaxSNP.lemma_7_1_aLet be an instance of 3-OCCURRENCE MAX3SAT with variables and clauses, and let be the scheduling instance constructed from it (v-jobs of length released at , c-jobs of length released at , a true and a false machine per variable). For every feasible schedule of , the truth assignment read off from the machines of the v-jobs satisfies
where is the number of clauses satisfied by and is the total completion time of .
This is the direction of the reduction that maps schedules back to truth assignments without losing more than the schedule's excess over .
Formalization Note The inequality is stated over the reals, so no natural-number subtraction occurs. The hypothesis that is a valid instance includes the at-most-three-occurrences condition of the page and the two conventions described in the definitions file (clauses have one to three literals, every variable occurs).
import Mathlib import Definitions.Def_SkutellaCQP_MaxSNP_Setting
namespace SkutellaCQP.MaxSNP
/-- Lemma 7.1 a) (p. 32). For every feasible schedule `S` of `R(I)`, the truth assignment
`SAT(S)` satisfies at least `4n + 4m − VAL(S)` clauses of `I`. -/
theorem lemma_7_1_a {n m : ℕ} (I : Occ3Max3Sat n m) (hI : I.IsValid)
(S : Sched n m) (hS : Feasible I S) :
(4 * n + 4 * m : ℝ) - VAL S ≤ satCount I (SAT S) := by sorry
end SkutellaCQP.MaxSNP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.