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 humans.
Add to your Cargo.toml:
[dependencies]
problemreductions = "0.2"Install the pred command-line tool for exploring the reduction graph from your terminal:
cargo install problemreductions-cliOr build from source:
git clone https://github.com/CodingThrust/problem-reductions
cd problem-reductions
make cli # builds target/release/predSee the Getting Started guide for usage examples, the reduction workflow, and CLI usage.
The pred CLI includes a built-in MCP server for AI assistant integration (Claude Code, Cursor, Windsurf, OpenCode, etc.).
Add to your client's MCP config file:
{"mcpServers": {"problemreductions": {"command": "pred", "args": ["mcp"]}}}| Client | Config file |
|---|---|
| Claude Code / Desktop | .mcp.json or ~/.claude/mcp.json |
| Cursor | .cursor/mcp.json |
| Windsurf | ~/.codeium/windsurf/mcp_config.json |
| OpenCode | opencode.json (use {"mcp": {"problemreductions": {"type": "local", "command": ["pred", "mcp"]}}}) |
See the MCP documentation for available tools, prompts, and full configuration details.
No programming experience required. You contribute domain knowledge; we handle the implementation.
- 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.
- We implement it — for reasonable requests, maintainers tag the issue
implementand AI agents generate a tested implementation. - We present it to you — all issue contributors are invited to community calls (via Zulip), where maintainers walk through the implementation — documentation, CLI behavior, correctness — and you provide 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
/proposeto 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.
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.
- 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.
MIT License - see LICENSE for details.