reduction-builder
// Construct and verify polynomial-time reductions between computational problems
$ git log --oneline --stat
stars:384
forks:73
updated:March 4, 2026
SKILL.mdreadonly
SKILL.md Frontmatter
namereduction-builder
descriptionConstruct and verify polynomial-time reductions between computational problems
allowed-toolsBash,Read,Write,Edit,Glob,Grep
metadata[object Object]
Reduction Builder
Purpose
Provides expert guidance on constructing polynomial-time reductions for NP-completeness proofs and problem classification.
Capabilities
- Gadget library for common reductions (3-SAT, Vertex Cover, etc.)
- Reduction verification (correctness in both directions)
- Polynomial-time verification
- Visualization of gadget constructions
- Generate reduction documentation
- Chain multiple reductions
Usage Guidelines
- Problem Analysis: Understand source and target problem structures
- Gadget Selection: Choose or design appropriate gadgets
- Reduction Construction: Build the polynomial-time mapping
- Correctness Proof: Prove both directions of the reduction
- Time Analysis: Verify polynomial running time
Tools/Libraries
- Graph visualization
- LaTeX documentation
- Formal verification tools