[](https://crates.io/crates/problemreductions)
[](https://github.com/CodingThrust/problem-reductions/actions/workflows/ci.yml)
[](https://codecov.io/github/CodingThrust/problem-reductions)
[](https://codingthrust.github.io/problem-reductions/)
A Rust library for NP-hard problem definitions and reductions. We aim to implement [100+ problems and reduction rules](https://codingthrust.github.io/problem-reductions/) 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](https://codingthrust.github.io/problem-reductions/reductions.pdf) for humans.
## Installation
### As a library
Add to your `Cargo.toml`:
```toml
[dependencies]
problemreductions = "0.2"
```
### CLI tool
Install the `pred` command-line tool for exploring the reduction graph from your terminal:
```bash
cargo install problemreductions-cli
```
Or build from source:
```bash
git clone https://github.com/CodingThrust/problem-reductions
cd problem-reductions
make cli # builds target/release/pred
```
See the [Getting Started](https://codingthrust.github.io/problem-reductions/getting-started.html) guide for usage examples, the reduction workflow, and [CLI usage](https://codingthrust.github.io/problem-reductions/cli.html).
## MCP Server (AI Integration)
The `pred` CLI includes a built-in [MCP](https://modelcontextprotocol.io/) server for AI assistant integration (Claude Code, Cursor, Windsurf, OpenCode, etc.).
Add to your client's MCP config file:
```json
{"mcpServers": {"problemreductions": {"command": "pred", "args": ["mcp"]}}}
```
| 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](https://codingthrust.github.io/problem-reductions/mcp.html) for available tools, prompts, and full configuration details.
## Contributing
**No programming experience required.** You contribute domain knowledge; we handle the implementation.
1. **File an issue** — use the [Problem](https://github.com/CodingThrust/problem-reductions/issues/new?template=problem.md) or [Rule](https://github.com/CodingThrust/problem-reductions/issues/new?template=rule.md) 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](https://problem-reductions.zulipchat.com/), 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](https://codingthrust.github.io/problem-reductions/reductions.pdf).
> **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](https://codingthrust.github.io/problem-reductions/design.html) guide. Run `make help` to see available developer commands.
## Acknowledgments
This project draws inspiration from the following packages:
- **[ProblemReductions.jl](https://github.com/GiggleLiu/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](https://github.com/QuEraComputing/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](https://github.com/tamuhey/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](https://github.com/REA1/karp)** — A DSL (built on Racket) for writing and testing Karp reductions between NP-complete problems ([PLDI 2022 paper](https://dl.acm.org/doi/abs/10.1145/3519939.3523732)). Focused on education and proof verification rather than a solver pipeline.
- **[Complexity Zoo](https://complexityzoo.net/)** — Comprehensive catalog of 550+ computational complexity classes (Scott Aaronson).
- **[A Compendium of NP Optimization Problems](https://www.csc.kth.se/tcs/compendium/)** — 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](LICENSE) for details.