Skill

role-algorithms:computational-complexity

Analyzes computational complexity — P vs NP classification, NP-completeness proofs and reductions, approximation algorithms (PTAS, FPTAS) with provable guarantees, parameterized complexity (FPT, kernelization), randomized algorithms (Las Vegas, Monte Carlo), and practical heuristics for intractable problems. Use when classifying hardness, proving reductions, or selecting between exact and heuristic approaches.

Install

npx claudepluginhub rnavarych/alpha-engineer --plugin role-algorithms

Tool Access

This skill is limited to using the following tools:

ReadGrepGlobBash

Preview

- Classifying a problem as P, NP-complete, or NP-hard before choosing an algorithm

Supporting Assets

references/approximation-and-fpt.mdreferences/complexity-classes.mdreferences/randomized-and-heuristics.md

SKILL.md

Similar Skills

skill-lookup

Searches, retrieves, and installs Agent Skills from prompts.chat registry using MCP tools like search_skills and get_skill. Activates for finding skills, browsing catalogs, or extending Claude.

prompts.chat

157.6k

prompt-lookup

Searches prompts.chat for AI prompt templates by keyword or category, retrieves by ID with variable handling, and improves prompts via AI. Use for discovering or enhancing prompts.

prompts.chat

157.6k

Agent Development

6 files

Guides agent creation for Claude Code plugins with file templates, frontmatter specs (name, description, model), triggering examples, system prompts, and best practices.

plugin-dev

83.2k

Stats

Parent Repo Stars9

Parent Repo Forks0

Last CommitMar 3, 2026

Actions

View Source View Plugin View on GitHub View README

role-algorithms:computational-complexity

When to use

Classifying a problem as P, NP-complete, or NP-hard before choosing an algorithm

Proving a problem is NP-complete via polynomial-time reduction

Selecting between exact, approximation, FPT, or heuristic approaches

Designing approximation algorithms with provable guarantees (PTAS, FPTAS)

Deciding when randomized algorithms (Las Vegas vs Monte Carlo) are appropriate

Identifying when a parameter makes an otherwise hard problem tractable (FPT)

Core principles

Classify before solving — knowing a problem is NP-hard changes the entire strategy

Reduction direction matters — reduce FROM a known hard problem TO yours to prove hardness

Approximation ratio is a guarantee, not a hope — an unproven heuristic is not an approximation algorithm

Small parameter = FPT opportunity — exponential in k is fine when k ≤ 20

Amplify randomized correctness — repeat Monte Carlo k times to push error below 2^(-k)

Reference Files

references/complexity-classes.md — P, NP, NP-complete, NP-hard, PSPACE definitions; common NPC problems; reduction technique step-by-step; recognizing NP-hard problems in practice

references/approximation-and-fpt.md — approximation ratios, classic results table, PTAS/FPTAS definitions, inapproximability bounds, FPT algorithms, kernelization, treewidth parameter

references/randomized-and-heuristics.md — Las Vegas vs Monte Carlo, amplification, MCMC, local search, simulated annealing, genetic algorithms, when-to-use decision table

Computational Complexity

When to use

Classifying a problem as P, NP-complete, or NP-hard before choosing an algorithm
Proving a problem is NP-complete via polynomial-time reduction
Selecting between exact, approximation, FPT, or heuristic approaches
Designing approximation algorithms with provable guarantees (PTAS, FPTAS)
Deciding when randomized algorithms (Las Vegas vs Monte Carlo) are appropriate
Identifying when a parameter makes an otherwise hard problem tractable (FPT)

Core principles

Classify before solving — knowing a problem is NP-hard changes the entire strategy
Reduction direction matters — reduce FROM a known hard problem TO yours to prove hardness
Approximation ratio is a guarantee, not a hope — an unproven heuristic is not an approximation algorithm
Small parameter = FPT opportunity — exponential in k is fine when k ≤ 20
Amplify randomized correctness — repeat Monte Carlo k times to push error below 2^(-k)

Reference Files

references/complexity-classes.md — P, NP, NP-complete, NP-hard, PSPACE definitions; common NPC problems; reduction technique step-by-step; recognizing NP-hard problems in practice
references/approximation-and-fpt.md — approximation ratios, classic results table, PTAS/FPTAS definitions, inapproximability bounds, FPT algorithms, kernelization, treewidth parameter
references/randomized-and-heuristics.md — Las Vegas vs Monte Carlo, amplification, MCMC, local search, simulated annealing, genetic algorithms, when-to-use decision table