Lemma 24 — Reduction to distinct integer points
DisprovedExactKMeans.ProductReduction.lemma_24Let a,b≥1 and q=ab≥2. The graph has N vertices and q color classes, possibly empty. No equal-size or odd-size assumption is made.
Lemma 24 (Reduction to distinct integer points). For integers a, b ∈ N+, there is a polynomial-time reduction from an instance (G, q) of Multicolored Clique with q = ab ≥ 2, N = |V(G)|, to an instance (X, k) of Euclidean k-means on distinct points X ⊆ Z^d with coordinates of absolute value O(N^168) and an integer cost budget C̄_tot = O(N^373) satisfying n = |X| = O(N^55), d = 2b + 1, k = 2a. The total binary encoding length is L = O(N^56 log N). The graph G has a multicolored clique of size q if and only if OPT_k(X) ≤ C̄_tot.
All hidden constants are replaced by one C uniform in a,b and G. A single machine writes the full output instance in polynomial input length. N is the original graph order; no normalization or nonempty-color assumption is added.
Differences from the source:
- encoding: bit-RAM computation → published multitape Turing-machine execution with an explicit step bound; reason: polynomial simulations between the bit models are absorbed by the absolute exponent constant and computable parameter factors; Lemma 24 asserts polynomial time in either model
- encoding: asymptotic bounds in N → the same bounds with max(2,N) as their base; reason: this specifies small inputs without log(0) or a zero time budget, and is identical for every N≥2
- encoding: Multicolored Clique on graphs with a color partition → the published pMCC predicate on valid encoded graphs, with a promise on code validity; reason: all graph instances, including empty color classes, remain included; the source gives no malformed-string requirement
- encoding: O(N¹⁶⁸), O(N³⁷³), O(N⁵⁵), O(N⁵⁶ log N) and polynomial time → one positive natural constant C and degree e before all inputs; reason: taking the maximum of finitely many absolute constants gives the same uniform asymptotic assertions; signed coordinates and threshold use binary magnitudes
- encoding: a reduction for given a,b producing a k-means instance → one machine reading a and b in binary before the graph code, whose output instance also satisfies 1 ≤ k ≤ n; reason: a and b are the reduction's parameters; §2 (printed p. 7) fixes 1 ≤ k ≤ n for every k-means instance
import Definitions.Def_ExactKMeans_ProductReduction_Computation open scoped BigOperators Classical open Finset open ExactKMeans.ProductReduction
namespace ExactKMeans.ProductReduction
theorem lemma_24 :
∃ (A : TM) (C e : ℕ), 0 < C ∧
∀ (a b : ℕ), 0 < a → 0 < b → 2 ≤ a*b →
∀ (G : NPGraph.Graph) (cols : List ℕ), ValidMCC G (a*b) cols →
∃ I : IntegerInstance,
I.d = 2*b+1 ∧ I.k = 2*a ∧ 1 ≤ I.n ∧ I.k ≤ I.n ∧ Function.Injective I.points ∧
(∀ i j, (I.points i j).natAbs ≤ C * (max 2 G.order)^168) ∧
I.threshold.natAbs ≤ C * (max 2 G.order)^373 ∧
I.n ≤ C * (max 2 G.order)^55 ∧
I.code.length ≤ C * (max 2 G.order)^56 * Nat.log 2 (max 2 G.order) ∧
(ParityCubes.pMCC (MCCCode G (a*b) cols) (a*b) ↔ I.yes) ∧
OutputsWithin A (binaryNat a ++ binaryNat b ++ MCCCode G (a*b) cols) I.code
(C * ((binaryNat a ++ binaryNat b ++ MCCCode G (a*b) cols).length + 1)^e) := by sorry
end ExactKMeans.ProductReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.