Search papers, labs, and topics across Lattice.
This paper introduces a system for automating the creation of polynomial-time reductions between NP-hard problems, enabling a single interface to route problems to various solvers. They achieve this by using harness engineering, which combines a no-code contribution route, a multilayer verification stack with AI agents, and an automated implementation pipeline. The resulting tool, built in three months, comprises a library of 100+ problem types and 200+ reduction rules in 170k+ lines of Rust, demonstrating the potential of AI coding agents for large-scale software development.
AI agents, guided by a carefully engineered harness, can build and verify complex software libraries at a scale and pace previously unattainable for tasks like polynomial-time problem reductions.
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 designing constraints, verification systems, and feedback loops that channel AI coding agents, can overcome this barrier. Our harness combines a no-code contribution route for domain experts, a multilayer verification stack ranging from type-level checks to agentic feature tests (AI agents role-playing as end users), and a fully automated implementation-review-integration pipeline. In about three months, we built a command-line tool backed by a library of 100+ problem types and 200+~reduction rules in over 170k lines of Rust. The result suggests that a well-engineered harness lets agents build well-tested software at a scale and pace beyond prior reduction-library efforts. Because the reduction graph composes transitively, a new solver registered for any single problem type instantly becomes available to every problem connected by a reduction path. The source code is available at https://github.com/CodingThrust/problem-reductions.
