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.
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, you can file issues interactively:
File an issue on CodingThrust/problem-reductions, using the "Model" issue template, about the Closest Vector Problem. Brainstorm with me.
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.
