Theorem 4.5, p. 159 — for p ≥ 2, J′(F) has optima, all binary; x(F) = 1 iff (3.3) holds; value 2n_p + 1 − x(F)
ProvedJeroslowMLP.Value.theorem_4_5Let , let be a propositional formula over blocks of sizes , and let be the set of optimal solutions of the -level game . Then:
- ;
- at every all atom variables and all are binary;
- at every , if and only if the sentence (3.3) is true;
- the value of (player 's criterion on ) is
- if (3.3) is true, a vector is player 's block in some optimal solution if and only if is binary and
holds, where is the truth valuation of .
The paper states this as: "the level game has a binary value, and this value is zero iff . Furthermore, all optimal solutions are binary vectors." The theorem reduces truth of sentences to the value of a linear multi-level program with fixed criteria, so computing such values is -hard.
Formalization Note The paper's "binary value, zero iff " describes the explicit term of ; the term is the same constant in every optimum (the proof of Lemma 4.4 computes or ). Items 3 and 4 state the value exactly. "All optimal solutions are binary vectors" is read as the atom variables and the : the gadget variable of (4.1) equals at . Item 5 is the theorem's last sentence ("the additional fact emerged in the proof of Lemma 4.4"). Player is index p of the game and its block is ⟨p - 1, _⟩.
import Mathlib import Definitions.Def_JeroslowMLP_Value_Game
namespace JeroslowMLP.Value
open MultilevelProgram GVar
theorem theorem_4_5 (p : ℕ) (hp : 2 ≤ p) (n : Fin p → ℕ) (F : Formula (Atom p n)) :
let S := (jGame p n F).solSet (p + 1)
let top : Fin p := ⟨p - 1, by omega⟩
S.Nonempty ∧
(∀ x ∈ S, (∀ a, IsBinary (x (atom a))) ∧ (∀ g, IsBinary (x (node g)))) ∧
(∀ x ∈ S, (xF x = 1 ↔ Sentence33 p n F)) ∧
(Sentence33 p n F → (jGame p n F).HasValue (p + 1) (2 * (n top : ℝ))) ∧
(¬ Sentence33 p n F → (jGame p n F).HasValue (p + 1) (2 * (n top : ℝ) + 1)) ∧
(Sentence33 p n F → ∀ w : Fin (n top) → ℝ,
((∃ x ∈ S, ∀ j, x (atom ⟨top, j⟩) = w j) ↔
((∀ j, IsBinary (w j)) ∧
QHolds p n F (p - 1) (fun a => if h : a.1 = top then
decide (w (Fin.cast (by rw [h]) a.2) = 1) else false)))) := by sorry
end JeroslowMLP.Value
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.