A Rust library for NP-hard problem definitions and reductions. We aim to implement 100+ problems and reduction rules between them, with automatic reduction path search. Built with AI assistance.

This infrastructure aims to solve two problems:

• Given a hard problem $A$, reduce it to the most viable problem $B$, to be solved efficiently with an external solver.
• Given a solver $S$ for problem $B$, explore how efficiently it can be used for solving other problems.

Download PDF manual for the full theory and proofs.

For Terminal Users

Install the pred CLI tool:

cargo install problemreductions-cli

Or build from source:

git clone https://github.com/CodingThrust/problem-reductions
cd problem-reductions
make cli    # builds target/release/pred

Try it out:

# Show the Consecutive Block Minimization model (alias: CBM)
pred show CBM

# Create and solve a small CBM instance
pred create CBM --matrix '[[true,false,true],[false,true,true]]' --bound 2 \
  | pred solve - --solver brute-force

See the full CLI guide for all commands and examples.

For AI Agent Users

Paste into Claude Code or Codex:

Clone https://github.com/CodingThrust/problem-reductions,
build the pred CLI with `make cli`,
then run /find-solver to help me find a solver for my scheduling problem.

Other prompts to try:

What problems can my QUBO solver handle? Use /find-problem to explore.

I know a reduction from Vertex Cover to Independent Set. Use /propose to file an issue.

See AI Agent Skills for more prompts.

Contributing

No programming experience required. You contribute domain knowledge; we handle the implementation.

1. File an issue — use the Problem or Rule template. Describe the problem or reduction you have in mind — the template guides you through the details.
2. We implement it — for reasonable requests, maintainers tag the issue implement and AI agents generate a tested implementation.
3. We present it to you — all issue contributors are invited to our weekly community call (Tuesdays 10:00 HKT) via Zulip, where we walk through implementations, resolve open issues, and collect feedback.

Which rules matter most? Run cargo run --example detect_isolated_problems and cargo run --example detect_unreachable_from_3sat to see which problems are disconnected or lack NP-hardness proof chains from 3-SAT. Rules that connect isolated problems or complete proof chains are especially valuable.

Authorship: contribute 10 non-trivial reduction rules and you'll be added to the author list of the paper.

Tip: If you use Claude Code / OpenCode / Codex, run /propose to file issues interactively — it guides you one question at a time, suggests the most needed reductions based on graph topology, and runs quality checks before filing:

/propose              # brainstorm a new model or rule
/propose model        # propose a new problem
/propose rule         # propose a new reduction

If you prefer to implement yourself, see the Design guide. Run make help to see available developer commands.

Acknowledgments

This project draws inspiration from the following packages:

• ProblemReductions.jl — Julia library for computational problem reductions. Our problem trait hierarchy, reduction interface (ReduceTo/ReductionResult), and graph-based reduction registry are directly inspired by this package.
• UnitDiskMapping.jl — Julia package for mapping problems to unit disk graphs. Our unit disk graph (King's subgraph / triangular lattice) reductions and the copy-line method are based on this implementation.
• qubogen — Python library for generating QUBO matrices from combinatorial problems. Our QUBO reduction formulas (Vertex Cover, Graph Coloring, Set Packing, Max-2-SAT, binary ILP) reference the implementations in this package.

Related Projects

• Karp — A DSL (built on Racket) for writing and testing Karp reductions between NP-complete problems (PLDI 2022 paper). Focused on education and proof verification rather than a solver pipeline.
• Complexity Zoo — Comprehensive catalog of 550+ computational complexity classes (Scott Aaronson).
• A Compendium of NP Optimization Problems — Online catalog of NP optimization problems with approximability results (Crescenzi & Kann).
• Computers and Intractability (Garey & Johnson, 1979) — The classic reference cataloging 300+ NP-complete problems with reductions. The most cited book in computer science.

License

MIT License - see LICENSE for details.