Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems

arXiv:2604.11535v1 Announce Type: new Abstract: Solving an NP-hard optimization problem often requires reformulating it for a specific solver -- quantum hardware, a commercial optimizer, or a domain heuristic. A tool for polynomial-time reductions between hard problems would let practitioners route any supported problem to any supported solver through a single interface. Building such a library at scale, however, has remained out of reach. We show that harness engineering, the practice of design