Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.3 (companion theorem; not used in the proof of the goal) — chordal Max-Cut hardness

Open
IntervalMaxCutEPTAS.Scheme.Supplement.theorem_1_3

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorygraph-theorymax-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For every real ε>0\varepsilon>0ε>0, the existence of a polynomial-time deterministic Max-Cut approximator of factor 84/85+ε84/85+\varepsilon84/85+ε on unweighted chordal graphs implies equality of the standard language classes

P=NP.\mathbf P=\mathbf{NP}.P=NP.

The same implication holds when the guarantee is required only for graphs obtained from a split graph by adding independent degree-two vertices whose two neighbors in the split graph are adjacent. The approximator receives only the graph and returns its cut as an nnn-bit bitmap. The classes include empty and edgeless graphs, and every positive accuracy is covered, with no assumption of P≠NP\mathbf P\ne\mathbf{NP}P=NP, UGC, SSE or a free source-hardness proposition. This is an independent companion theorem to the base EPTAS.

Differences from the source:

  • encoding: NP-hardness as approximator implies P = NP → two implications to equality of the published PvsNP language classes, using their finite-alphabet polynomial-time TM2 transducers; reason: these are standard P and NP; no external hardness assertion is a hypothesis
  • encoding: ordinary simple graph input and a returned cut → self-delimiting binary n followed by the upper triangle, and exactly n cut bits; reason: these encodings have polynomially related lengths to standard graph encodings and contain no advice
  • encoding: a polynomial-time approximation algorithm on a promised graph class → a total polynomial-time string transducer whose guarantee is required only on the promised class; reason: invalid inputs can be validated and rejected and other inputs timed out after the algorithm’s polynomial bound; this does not change any promised instance
Preamble
import Mathlib
import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Supplement_Hardness

set_option autoImplicit false
Formal statement
namespace IntervalMaxCutEPTAS.Scheme.Supplement

/-- Theorem 1.3, PDF 4 (printed 3), proof PDF 27–28. The consequence is equality of the
published standard language classes; no source-hardness proposition is a hypothesis. -/
theorem theorem_1_3 (ε : ℝ) (hε : 0 < ε) :
    (PolynomialApproximation ((84 : ℝ) / 85 + ε) chordalClass → PvsNP.P = PvsNP.NP) ∧
    (PolynomialApproximation ((84 : ℝ) / 85 + ε) restrictedClass → PvsNP.P = PvsNP.NP) := by sorry

end IntervalMaxCutEPTAS.Scheme.Supplement
Source
Morteza Alimi, Hani Ahmadzadeh, STOC 2027 submission #636 (October 2026), Theorem 1.3, PDF p. 4 (printed p. 3)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me