Corollary 1.4 — a deterministic -approximation
ProvedDualSepClusterLP.deterministicApproximationA uniform deterministic algorithm returns a clustering within of the optimum on every complete unweighted signed graph, in time. The integer accuracy index requests ; this covers all positive real tolerances by rounding inverse accuracy up.
import Mathlib import Mathlib.Computability.TuringMachine.Computable import Definitions.Def_DualSepClusterLP_Setting
namespace DualSepClusterLP
/-- Corollary 1.4 at additive accuracy 1/(t+1). -/
theorem deterministicApproximation :
∃ (M : Turing.TM2ComputableAux Bool Bool) (A a b : ℕ),
(∀ k, Finite (M.tm.Γ k)) ∧
∀ (t n : ℕ) (G : Graph n), ∃ C : Clustering n,
Nonempty (Turing.TM2OutputsInTime M.tm
((graphInput t G).map M.inputAlphabet.symm)
(some ((partitionOutput C).map M.outputAlphabet.symm))
(2 ^ (A * (t+1)^a) * (n+1)^b)) ∧
∀ D : Clustering n,
2000 * (t+1) * disagreements G C ≤
(2773 * (t+1) + 2000) * disagreements G D := by sorry
end DualSepClusterLP
Read-back
What the Lean code literally says, in plain math · Codex (GPT-6)
There is one deterministic machine with finite stack alphabets and fixed natural constants A,a,b. For every t,n and graph the machine must output some partition's equality matrix in at most 2^{A(t+1)^a}(n+1)^b steps. The output's cost is at most (2773/2000+1/(t+1)) times the cost of every partition. An optimum of zero forces zero cost. The statement covers valid encodings, including the empty graph.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.