| Home | Publications | Projects | News | CV | GitHub · Google Scholar · Email |
A Rust library and CLI (pred) for NP-hard problem definitions, reductions, and routing across solvers
problem-reductions is a Rust infrastructure that catalogs 100+ computationally hard problems and 200+ reduction rules between them, exposed through a CLI tool called pred. Built with agentic coding workflows, it answers two practical questions:
The reduction graph is transitive: registering a new solver for a single node immediately makes it available to every problem connected to it.

Figure 1 from the paper — a portion of the reduction graph. Nodes are problem types and directed edges are reductions. Registering a solver for any node propagates along outgoing paths to reachable problems.
pred CLIThe command-line tool provides a unified interface to:
At the core is a registry that stores problems as nodes and reductions as directed edges. A path-search routine finds the sequence of reductions from any source problem to a problem with a registered solver, composing per-edge forward/backward transformations to recover the original solution.
Quality-detection tools flag isolated or unreachable problems so coverage can be improved systematically.
| Package | Ecosystem |
|---|---|
| ProblemReductions.jl | Julia |
| UnitDiskMapping.jl | Julia |
| qubogen | Python |
Last updated November 1, 2026.