Przejdź do treści
Biblioteka skilli
Programowanie · Analiza

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.

Repozytorium
alpha-engineer ↗
Licencja
MIT
Ostatnia zmiana repozytorium
24.07.2026

Ocena i bezpieczeństwo

80/ 100Klasa: dobry
Format15 / 25
Frontmatter z nazwą i opisem, poprawna nazwa, opis do 1024 znaków, nazwa zgodna z folderem.
Odkrywalność25 / 25
Opis mówi, kiedy użyć skilla, ma sensowną długość i jest w 3. osobie.
Treść25 / 35
Co najmniej 150 słów i do 500 linii, nagłówki, listy kroków, przykłady albo kod.
Higiena15 / 15
Bez zaślepek typu TODO, bez ścieżek Windows, z licencją.
Ryzykobrak sygnałów w skanie
Pliki w paczce
4
Skrypty
0
Komentarze HTML
0
Adresy URL w SKILL.md
0
Przestarzałość

Brak sygnałów. Repozytorium zmienione 24.07.2026, bez odwołań do wycofanych modeli i API.

Licencja

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

  1. When to use
  2. Core principles
  3. Reference Files
Sekcje z nagłówków SKILL.md, w oryginale · 23 linii, 212 słów
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.

Uwagi i zgłoszenia

Wiadomość trafi do Bartosza Sokolińskiego. Adres e-mail jest potrzebny tylko do odpowiedzi. Szczegóły w polityce prywatności.