Theorem 2.1 — deterministic approximate dual separation
ProvedDualSepClusterLP.approximateSeparationFor each accuracy the algorithm either exhibits a subset that violates the original dual inequality or certifies dual feasibility after dividing the prices by one plus the requested error. Its running time is singly exponential in a polynomial of inverse accuracy and polynomial in the graph size and price bit length.
import Mathlib import Mathlib.Computability.TuringMachine.Computable import Definitions.Def_DualSepClusterLP_LinearProgram import Definitions.Def_DualSepClusterLP_SeparationEncoding
namespace DualSepClusterLP
/-- Theorem 2.1 at accuracy 1/(t+1). A genuine violation and scaled feasibility can both hold.
The machine may return either answer whenever its stated condition holds. -/
theorem approximateSeparation :
∃ (M : Turing.TM2ComputableAux Bool Bool) (A a b : ℕ),
(∀ k, Finite (M.tm.Γ k)) ∧
∀ (t n : ℕ) (G : Graph n) (q : Fin n → ℚ),
∃ result : Option (Finset (Fin n)),
Nonempty (Turing.TM2OutputsInTime M.tm
((separationInput t G q).map M.inputAlphabet.symm)
(some ((separationOutput result).map M.outputAlphabet.symm))
(2 ^ (A * (t+1)^a) * (n+(pricesBits q).length+1)^b)) ∧
match result with
| some S => subsetCost G S < ∑ i ∈ S, (q i : ℝ)
| none => DualFeasible G (fun i => (q i : ℝ) / (1 + 1 / ((t : ℝ) + 1))) := by sorry
end DualSepClusterLP
Read-back
What the Lean code literally says, in plain math · Codex (GPT-6)
One machine with finite stack alphabets and constants A,a,b must answer each encoded graph, signed rational price vector and accuracy index t in at most 2^{A(t+1)^a}(n+L+1)^b steps, with L the encoded price length. A returned set strictly violates an original inequality. The other reply certifies feasibility of prices divided by 1+1/(t+1). Both answers can be valid for the same input.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.