role-algorithms:computational-complexity
/role-algorithms:computational-complexity
Klasyfikuje trudność problemów obliczeniowych, dowodzi redukcji NP-zupełności i dobiera algorytmy przybliżone lub heurystyczne.
- Autor
- rnavarych ↗
- Repozytorium
- alpha-engineer ↗
- Licencja
- MIT
- Ostatnia zmiana repozytorium
- 24.07.2026
Ocena i bezpieczeństwo
- Pliki w paczce
- 4
- Skrypty
- 0
- Komentarze HTML
- 0
- Adresy URL w SKILL.md
- 0
Brak sygnałów. Repozytorium zmienione 24.07.2026, bez odwołań do wycofanych modeli i API.
MIT, otwarta: można używać i zmieniać, z zachowaniem informacji o autorze.
Co robi i kiedy
Klasyfikuje trudność problemów obliczeniowych, dowodzi redukcji NP-zupełności i dobiera algorytmy przybliżone lub heurystyczne.
Oryginalny opis (EN)
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.
Jak działa
- When to use
- Core principles
- Reference Files
Podgląd SKILL.md
--- 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
Pliki w paczce (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
Wersje
W bazie nie ma innych skilli o nazwie role-algorithms:computational-complexity.
Migawka bazy z 13.11.2026 · wersja paczki 6518436fafd7 (skrót SHA-256 całej paczki)
Pobrania w ostatnich 30 dniach: 0 · ranking
Zgłoś problem z tym skillem: szkodliwa treść, błędny opis albo prośba autora o usunięcie.
Podobne skille
- 90role-algorithms:algorithm-design
Projektuje algorytmy z analizą złożoności, dowodami poprawności i doborem paradygmatu, np. zachłannego lub programowania dynamicznego. - 100dpf-computational-thinking
Pomaga projektować algorytmy, które dają wymagany wynik przy zadanych ograniczeniach poprawności, zasobów i interakcji. - 100algorithms
Pomaga dobierać algorytmy i struktury danych, analizować złożoność Big-O oraz kompromisy czasu i pamięci, opierając się na podejściu Knutha. - 96complexity-management
Pomaga naprawić nieudaną bramkę złożoności kodu albo funkcję zbliżającą się do limitu.