문제 축소 기법의 확장: 계산적으로 어려운 문제에 대한 에이전트 기반 통합

Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems

NP-hard 최적화 문제를 해결하는 데는 종종 특정 솔버(양자 하드웨어, 상용 최적화 도구 또는 도메인 휴리스틱)에 맞게 문제를 재구성해야 합니다. 어려운 문제 간의 다항 시간 축소 기능을 제공하는 도구는 사용자가 단일 인터페이스를 통해 지원되는 모든 문제를 지원되는 모든 솔버로 연결할 수 있게 해줍니다. 그러나 이러한 라이브러리를 대규모로 구축하는 것은 어려움이 있었습니다. 본 연구에서는 제약 조건, 검증 시스템 및 피드백 루프를 설계하여 AI 코딩 에이전트를 제어하는 '하네스 엔지니어링' 기술이 이러한 장벽을 극복할 수 있음을 보여줍니다. 저희의 하네스는 도메인 전문가를 위한 노코드 기여 경로, 타입 수준 검사부터 에이전트 기반 기능 테스트(사용자 역할을 하는 AI 에이전트)에 이르는 다층 검증 스택, 그리고 완전히 자동화된 구현-검토-통합 파이프라인을 결합합니다. 약 3개월 동안, 저희는 100개 이상의 문제 유형과 200개 이상의 축소 규칙을 포함하는 17만 줄 이상의 Rust 코드로 구성된 라이브러리를 기반으로 하는 명령줄 도구를 구축했습니다. 그 결과는 잘 설계된 하네스를 통해 에이전트가 기존의 축소 라이브러리 노력보다 더 큰 규모와 속도로 잘 테스트된 소프트웨어를 구축할 수 있음을 시사합니다. 축소 그래프가 추이적으로 구성되기 때문에, 단일 문제 유형에 등록된 새로운 솔버는 축소 경로로 연결된 모든 문제에 즉시 사용 가능해집니다. 소스 코드는 https://github.com/CodingThrust/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.