Theorem 1.3 (companion theorem; not used in the proof of the goal) — chordal Max-Cut hardness
OpenIntervalMaxCutEPTAS.Scheme.Supplement.theorem_1_3complexity-theorygraph-theorymax-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every real , the existence of a polynomial-time deterministic Max-Cut approximator of factor on unweighted chordal graphs implies equality of the standard language classes
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 -bit bitmap. The classes include empty and edgeless graphs, and every positive accuracy is covered, with no assumption of , 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)