用AI自动化构建可扩展的难题转换库，让不同求解器无缝对接。
Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems
- 设计约束与反馈机制，驱动AI代理自动完成难题转换规则编写。
- 三个月内建成含100多个问题类型、200多条转换规则的完整库。
- 新求解器接入后，所有相关问题均可立即使用，适合算法工程师和科研人员。
解决NP-hard优化问题通常需将问题重构成特定求解器适配的形式——如量子硬件、商业优化器或领域启发式方法。若能构建一个可在多项式时间内实现难题间转换的工具，即可通过单一接口将任意支持的问题路由至任意支持的求解器。然而，大规模构建此类库一直难以实现。本文展示，通过构造工程（harness engineering）——即设计约束、验证系统与反馈循环以引导AI编码代理——可突破此瓶颈。我们的框架提供无代码贡献通道给领域专家，采用多层验证体系（从类型检查到由AI代理扮演用户进行功能测试），并实现全自动的代码编写-审查-集成流水线。在约三个月内，我们完成了包含100+问题类型、200+转换规则、超过17万行Rust代码的命令行工具与库。结果表明，经过良好工程化设计的框架，使代理能够以远超以往的规模与速度构建高质量软件。由于转换图具备传递性，只要为任一问题类型注册新求解器，所有经转换路径连接的问题均可立即使用该求解器。源代码见https://github.com/CodingThrust/problem-reductions。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。