Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 19 — no polynomial-time n^{1−ε}-approximation with overlapping group constraints unless P = NP

Open
FacilityIncompatibilities.UniformMatroid.Supplement.theorem_19

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

computational-complexityfacility-locationhardness-of-approximationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Fix ε>0\varepsilon>0ε>0. Consider facility location with unrestricted overlapping group constraints: nnn clients, mmm facilities, rational distances forming a (pseudo)metric, rational opening costs fi≥0f_i\ge0fi​≥0, and groups G1,…,GKG_1,\dots,G_KG1​,…,GK​ of clients with bounds bk∈Nb_k\in\mathbb Nbk​∈N, possibly overlapping and not necessarily covering the clients; an assignment σ:VC→S\sigma:V_C\to Sσ:VC​→S is feasible if no facility of SSS serves more than bkb_kbk​ clients of any GkG_kGk​.

Suppose there are a polynomial-time computable map A\mathcal AA on bit strings and a threshold NNN such that, for every such instance with n≥Nn\ge Nn≥N clients in which VFV_FVF​ is feasible, A\mathcal AA maps the input word to (the code of) a facility set SSS and a feasible assignment σ:VC→S\sigma:V_C\to Sσ:VC​→S with

∑i∈Sfi+∑jd(j,σ(j)) ≤ n1−ε⋅OPT.\sum_{i\in S}f_i+\sum_{j}d(j,\sigma(j))\ \le\ n^{1-\varepsilon}\cdot\mathrm{OPT}.i∈S∑​fi​+j∑​d(j,σ(j)) ≤ n1−ε⋅OPT.

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

This shows that the partition assumption of Definition 2 cannot be dropped: with overlapping groups the problem is as hard to approximate as graph coloring. For ε≥1\varepsilon\ge1ε≥1 the ratio is below 111 for n≥2n\ge2n≥2, so no such algorithm exists and the statement holds trivially, as in the source.

Formalization Note P\mathbf PP, NP\mathbf{NP}NP and polynomial-time computability are those of the published CookPvsNP_defs; "unless P=NP\mathbf P=\mathbf{NP}P=NP" is an implication whose hypothesis is the existence of the algorithm. Nothing about the inapproximability of chromatic number is assumed. n1−εn^{1-\varepsilon}n1−ε is the real power, OPT\mathrm{OPT}OPT is in ℝ≥0∞.

Differences from the source:

  • generalization: a polynomial-time n^{1−ε}-approximation on every instance → the ratio is required only on instances with at least N clients, N chosen together with the algorithm; reason: an algorithm in the source's sense satisfies the hypothesis with N = 0, so the Lean statement implies the source's
  • generalization: metric distances → a pseudometric (distinct points may be at distance 0); reason: every metric satisfies these axioms, and the paper's own reduction co-locates all points
  • encoding: "admits no polynomial-time n^{1−ε}-approximation unless P = NP" → (∃ polynomial-time computable Alg : List Bool → List Bool with the ratio, outputting an encoded feasible solution) → P = NP, with Cook's P and NP; reason: the standard reading of "unless P = NP"
  • encoding: groups and bounds b_k → a list of pairs (G_k ⊆ Fin n, b_k ∈ ℕ) written in the input word; V_F feasible as a hypothesis; reason: a cardinality bound is equivalent to its integer part; instances without any feasible solution have no approximate solution to output (standing assumption, printed p.2)
Preamble
import Mathlib
import Definitions.Def_FacilityIncompatibilities_UniformMatroid_Supplement_Hardness

open scoped ENNReal
Formal statement
namespace FacilityIncompatibilities.UniformMatroid.Supplement

/-- **Theorem 19** (printed p.23 / PDF p.24): for every fixed `ε > 0`, facility location with
unrestricted overlapping group constraints admits no polynomial-time `n^{1−ε}`-approximation
unless `P = NP`, where `n` is the number of clients.

Stated as: if some polynomial-time computable map `Alg` on bit strings and some threshold `N`
are such that, on every encoded instance with at least `N` clients (metric data, `f ≥ 0`,
arbitrary possibly overlapping groups, `V_F` feasible), `Alg` outputs the code of a feasible
solution `(S, σ)` of cost at most `n^{1−ε} · OPT`, then `P = NP`. -/
theorem theorem_19 (ε : ℝ) (hε : 0 < ε) :
    (∃ (Alg : List Bool → List Bool) (N : ℕ), CookPvsNP.PolyTimeComputable Alg ∧
      ∀ E : GroupEncodedInstance, N ≤ E.n → E.toGen.Valid →
        E.toGen.IsFeasible Finset.univ →
        ∃ (S : Finset (Fin E.m)) (σ : Fin E.n → Fin E.m),
          Alg E.encode = encodeSolution S σ ∧ E.toGen.IsFeasibleAssignment S σ ∧
          ENNReal.ofReal (E.toGen.solCost S σ) ≤
            ENNReal.ofReal ((E.n : ℝ) ^ (1 - ε)) * E.toGen.OPT) →
    PEqNP := by sorry

end FacilityIncompatibilities.UniformMatroid.Supplement
Source
Pengfei Wu, Zachary Friggstad, Facility Location with Customer Incompatibilities, STOC 2027 submission #664 (October 2026), SHA-256 e95d28b65476bd15332cddbb49bb8bfb3c370bb260b03d92b35425595cdb7ab3, Theorem 19, Appendix B.1, printed p.23 / PDF p.24 (proof printed pp.23–24 / PDF pp.24–25)

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