The Aaronson–Pollack bag of entropies is strongly NP-complete, exactly and under bounded noise

Aaronson and Pollack (2022) asked whether reconstructing a graph from an unlabelled 'bag' of entanglement entropies of contiguous boundary regions becomes NP-hard. We show that the problem, Bag-SSA (given a multiset of N choose 2 non-negative rationals, can they be arranged as a Kalmanson metric?), is strongly NP-complete. The hardness persists under the promise that the data come from a holographic state, and it is robust to additive noise: for every fixed error epsilon it remains strongly NP-complete, and it is hard for every epsilon < u/3 on instances whose values are multiples of u, the bound u/3 being tight for the construction. As a corollary, Bag-SSA admits no pseudo-polynomial algorithm unless P = NP, which separates it from turnpike. The reduction is from Numerical Matching with Target Sums; explicit counterexamples show that the gadget fails at m = 2, m = 5 and m = 7, sizes the reduction handles by enumeration, so the threshold m >= 8 is sharp for the construction. The combinatorial core of the reduction (Lemmas 6-12) is verified formally in the Lean 4 proof assistant with Mathlib, with no sorry and only the standard axioms. The deposit contains the paper, its LaTeX source and the supplementary code, scripts, outputs, counterexample matrices and Lean formalisation.