home / skills / a5c-ai / babysitter / reduction-builder

reduction-builder skill

safe

/plugins/babysitter/skills/babysit/process/specializations/domains/science/computer-science/skills/reduction-builder

This skill helps you construct and verify polynomial-time reductions between problems, guiding gadget selection, correctness proofs, and documentation.

npx playbooks add skill a5c-ai/babysitter --skill reduction-builder

Review the files below or copy the command above to add this skill to your agents.

Files (1)

SKILL.md

1.1 KB

---
name: reduction-builder
description: Construct and verify polynomial-time reductions between computational problems
allowed-tools:
  - Bash
  - Read
  - Write
  - Edit
  - Glob
  - Grep
metadata:
  specialization: computer-science
  domain: science
  category: complexity-theory
  phase: 6
---

# 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

1. **Problem Analysis**: Understand source and target problem structures
2. **Gadget Selection**: Choose or design appropriate gadgets
3. **Reduction Construction**: Build the polynomial-time mapping
4. **Correctness Proof**: Prove both directions of the reduction
5. **Time Analysis**: Verify polynomial running time

## Tools/Libraries

- Graph visualization
- LaTeX documentation
- Formal verification tools

Overview

This skill helps researchers and engineers construct and verify polynomial-time reductions between computational problems. It provides a library of reduction gadgets, tools to verify correctness and polynomial runtime, and utilities to document and visualize constructions. Use it to build rigorous NP-completeness proofs, chain reductions, and produce reproducible reduction artifacts.

How this skill works

The skill inspects source and target problem specifications and suggests or assembles gadgets mapped to problem components. It verifies correctness by checking equivalence in both directions and performs complexity analysis to ensure the mapping runs in polynomial time. It can render gadget diagrams, produce LaTeX-ready documentation, and export step-by-step reduction proofs.

When to use it

When proving NP-hardness or NP-completeness of a decision problem
When converting an algorithmic problem into another via polynomial-time mapping
When you need rigorous, checkable correctness proofs for reductions
When chaining several known reductions into a composite transformation
When preparing publication-ready diagrams and documentation for a reduction

Best practices

Start by formalizing input and output encodings for both problems
Reuse standard gadget templates (3-SAT, Vertex Cover, Clique) when possible
Provide both forward and backward correctness arguments explicitly
Include a clear time-complexity accounting for each construction step
Visualize gadgets and identify corner cases with small-instance tests

Example use cases

Prove a new graph problem is NP-complete by reducing from 3-SAT using clause and variable gadgets
Chain reductions from SAT -> Vertex Cover -> Dominating Set to transfer hardness results
Generate LaTeX documentation and diagrams for a conference submission
Verify that a proposed mapping runs in polynomial time and preserves solutions
Create unit-testable gadget instances to catch subtle encoding errors

FAQ

Can the skill verify time complexity automatically?

Yes — it analyzes each construction step and reports a polynomial bound or flags non-polynomial operations for review.

Does it handle both decision and optimization problems?

Primarily designed for decision problems and NP-completeness proofs, but it supports reductions that preserve approximation structure when documented explicitly.