Lemma 3.1, p. 150 — for binary atoms, L_F has a unique binary solution w, and F is true iff x(F) = 1
ProvedJeroslowMLP.Value.lemma_3_1integer-programminglinear-inequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1propositional-logic
Let be a propositional formula over blocked atoms, and let be a truth assignment of the atoms; set each atom variable to if is true and otherwise. Then:
- there is exactly one binary assignment of the node variables such that satisfies ;
- for every binary satisfying with these atom values,
This is the correctness of the linear encoding of a formula: on binary inputs, computes .
Formalization Note "Unique binary assignment" is unique existence among binary node vectors. If is atomic there are no node variables and is the atom's variable.
Preamble
import Mathlib import Definitions.Def_JeroslowMLP_Value_Formula import Definitions.Def_JeroslowMLP_Value_Multilevel
Formal statement
namespace JeroslowMLP.Value
theorem lemma_3_1 (p : ℕ) (n : Fin p → ℕ) (F : Formula (Atom p n)) (α : Atom p n → Bool) :
(∃! w : F.Node → ℝ, (∀ g, IsBinary (w g)) ∧
F.LSys (fun a => if α a then 1 else 0) w) ∧
∀ w : F.Node → ℝ, (∀ g, IsBinary (w g)) →
F.LSys (fun a => if α a then 1 else 0) w →
(F.eval α = true ↔ F.nodeVal (fun a => if α a then 1 else 0) w = 1) := by sorry
end JeroslowMLP.Value
Source
Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Programming 32 (1985), p. 150, Lemma 3.1, (3.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.