Skip to content
Skills Library
Programming · Analysis

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.

Licence
MIT
Last repository change
24.07.2026

Assessment and security

80/ 100Class: good
Format15 / 25
Frontmatter with name and description, valid name, description up to 1,024 characters, name matching the folder.
Discoverability25 / 25
Description explains when to use the skill, has a reasonable length and uses third person.
Content25 / 35
At least 150 words and at most 500 lines, headings, step lists, examples or code.
Hygiene15 / 15
No placeholders such as TODO, no Windows paths, with a licence.
Riskno signals detected in the scan
Files in this package
4
Scripts
0
HTML comments
0
URLs in SKILL.md
0
Deprecation

No signals detected. Repository changed on 24.07.2026, without references to retired models or APIs.

Licence

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

  1. When to use
  2. Core principles
  3. Reference Files
Original SKILL.md headings · 23 lines, 212 words
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.

Feedback and reports

Your message goes to Bartosz Sokoliński. An email address is needed only for a reply. See the privacy policy.