p. 10, system (4) — feasibility is membership in D(C)
ProvedKarpPapadimitriou.Generator.system4_iff_decisioncombinatorial-optimizationlinear-feasibilityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a generator for , let , let , and let . System (4) consists of and all inequalities in for this . It satisfies
This is the optimization-to-feasibility equivalence on which the decision algorithm operates.
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_Generator_Oracle
Formal statement
namespace KarpPapadimitriou.Generator
/-- System (4) is feasible precisely when the encoded threshold instance belongs to `D(C)`. -/
theorem system4_iff_decision (C : COP) (gen : Oracle C)
(hgen : IsGenerator C gen) (z : List Bool) (hz : z ∈ C.L)
(c : Fin (C.n z) → ℤ) (k : ℤ) :
(∃ x : Fin (C.n z) → ℚ,
(k : ℚ) ≤ dotQ c x ∧
∀ f g, (⟨z, (f, g)⟩ : Triple C) ∈ FG C gen → dotQ f x ≤ (g : ℚ)) ↔
encDInput z c k ∈ DLang C := by sorry
end KarpPapadimitriou.Generator
Source
Karp & Papadimitriou, On linear characterizations of combinatorial optimization problems, MIT/LCS/TM-154 (Feb. 1980), p. 10, proof of Theorem 2, system (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.