role-algorithms:computational-complexity
/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.
- Author
- rnavarych ↗
- Repository
- alpha-engineer ↗
- Licence
- MIT
- Last repository change
- 24.07.2026
Assessment and security
- Files in this package
- 4
- Scripts
- 0
- HTML comments
- 0
- URLs in SKILL.md
- 0
No signals detected. Repository changed on 24.07.2026, without references to retired models or APIs.
MIT, open: use and modify while retaining author attribution.
What it does and when to use it
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.
Original author description
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.
How it works
- When to use
- Core principles
- Reference Files
SKILL.md preview
--- name: role-algorithms:computational-complexity description: 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. allowed-tools: Read, Grep, Glob, Bash --- # 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 1. **Classify before solving** — knowing a problem is NP-hard changes the entire strategy 2. **Reduction direction matters** — reduce FROM a known hard problem TO yours to prove hardness 3. **Approximation ratio is a guarantee, not a hope** — an unproven heuristic is not an approximation algorithm 4. **Small parameter = FPT opportunity** — exponential in k is fine when k ≤ 20 5. **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
Files in this package (4)
- SKILL.md 2 KB
- references/approximation-and-fpt.md 3 KB
- references/complexity-classes.md 3 KB
- references/randomized-and-heuristics.md 2 KB
Versions
The database has no other skills named role-algorithms:computational-complexity.
Database snapshot: 13.11.2026 · package version 6518436fafd7 (SHA-256 digest of the entire package)
Downloads in the last 30 days: 0 · ranking
Report a problem with this skill: harmful content, incorrect descriptions or an author’s removal request.
Similar skills
- 90role-algorithms:algorithm-design
Designs algorithms with formal analysis — Big-O/Theta/Omega, amortized analysis, recurrence relations (Master theorem), correctness proofs (loop invariants, induction, reduction), and paradigm selection (greedy, divide-and-conquer, dynamic programming, backtracking). Use when… - 100dpf-computational-thinking
Computational Thinking (CMP) — Use when you need to construct algorithms that obtain the required answer within correctness, resource and interaction conditions. - 100algorithms
Use when selecting algorithms, analyzing complexity, or reasoning about data structure choices. Covers Big-O notation, space vs time tradeoffs, amortized analysis, and algorithmic problem-solving strategy based on Knuth's "The Art of Computer Programming." USE FOR: algorithm… - 96complexity-management
Use when the complexity gate fails or a function approaches a limit.