Agent-Skills.md

Agent Skills: Reduction Builder

Construct and verify polynomial-time reductions between computational problems

complexity-theoryID: a5c-ai/babysitter/reduction-builder

Repository

a5c-ai/babysitter
a5c-aiLicense: MIT
244

Install this agent skill to your local

pnpm dlx add-skill https://github.com/a5c-ai/babysitter/tree/HEAD/plugins/babysitter/skills/babysit/process/specializations/domains/science/computer-science/skills/reduction-builder

Skill Files

Browse the full folder contents for reduction-builder.

Download Skill

Loading file tree…

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

Skill Metadata

Name
reduction-builder
Description
Construct and verify polynomial-time reductions between computational problems

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