OpenSkillIndex← back to search
claude-codescience

Babysitter reduction-builder

Construct and verify polynomial-time reductions between computational problems

install
source · Clone the upstream repo
git clone https://github.com/a5c-ai/babysitter
Claude Code · Install into ~/.claude/skills/
T=$(mktemp -d) && git clone --depth=1 https://github.com/a5c-ai/babysitter "$T" && mkdir -p ~/.claude/skills && cp -r "$T/library/specializations/domains/science/computer-science/skills/reduction-builder" ~/.claude/skills/a5c-ai-babysitter-reduction-builder && rm -rf "$T"
manifest: library/specializations/domains/science/computer-science/skills/reduction-builder/SKILL.md
tags
#complexity-theory#np-completeness#reduction-verification#algorithm-design#formal-verification
source content

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