Szablon:Klasy złożoności
Z Wikipedii, wolnej encyklopedii
Ważne klasy złożoności
| Uważane za wykonalne | |
|---|---|
| Podejrzewane o niewykonalność | |
| Uważane za niewykonalne | |
| Hierarchie klas | |
| Rodziny klas |
Pozycje linkujące: 51, specjalne: 0, problemy?: 0, RAZEM: 51
Informacje diagnostyczne
- definicja szablonu
Szablon nawigacyjny- zadeklarowane kategorie
- 2
- informatyka
- podstawy matematyki
- kategorie w kodzie
- 0
- głębokość drzewa
- 1
- liczba liści
- 5
- prywatny CSS
- klasy_zlozonosci
Kanoniczne zestawienie parametrów
| nazwa = Klasy złożoności | tytuł = Ważne [[klasa złożoności|klasy złożoności]] | opis1 = Uważane za wykonalne | spis1 = * [[DLOGTIME]] * [[AC0|AC<sup>0</sup>]] * [[ACC0|ACC<sup>0</sup>]] * [[TC0|TC<sup>0</sup>]] * [[L (klasa złożoności)|L]] * [[SL (klasa złożoności)|SL]] * [[RL (klasa złożoności)|RL]] * [[NL (klasa złożoności)|NL]] * [[NC (klasa złożoności)|NC]] * [[SC (klasa złożoności)|SC]] * [[CC (klasa złożoności)|CC]] * [[Problem P|P]] ([[Problem P-zupełny|P-zupełność]]) * [[ZPP (klasa złożoności)|ZPP]] * [[RP (klasa złożoności)|RP]] * [[BPP (klasa złożoności)|BPP]] * [[BQP]] * [[APX]] | opis2 = Podejrzewane o niewykonalność | spis2 = * [[UP (klasa złożoności)|UP]] * [[Problem NP|NP]] ** [[Problem NP-zupełny|NP-zupełność]] ** [[Problem NP-trudny|NP-trudność]] ** [[Klasa Co-NP|co-NP]] ** [[Klasa Co-NPC|co-NP-zupełność]] * [[Protokół Arthura–Merlina|AM]] * [[QMA]] * [[PH (klasa złożoności)|PH]] * [[Parity P|⊕P]] * [[PP (klasa złożoności)|PP]] * [[Krzyżyk-P|#P]] ([[Krzyżyk-P-zupełność|#P-zupełność]]) * [[IP (klasa złożoności)|IP]] * [[PSPACE]] * ([[PSPACE-zupełność]]) | opis3 = Uważane za niewykonalne | spis3 = * [[EXPTIME]] * [[NEXPTIME]] * [[EXPSPACE]] * [[ELEMENTARY]] * [[PR (klasa złożoności)|PR]] * [[R (klasa złożoności)|R]] * [[RE (klasa złożoności)|RE]] * [[ALL (klasa złożoności)|ALL]] | opis4 = Hierarchie klas | spis4 = * [[Hierarchia wielomianowa]] * [[Hierarchia wykładnicza]] * [[Szybko rosnąca hierarchia|Hierarchia Grzegorczyka]] * [[Hierarchia arytmetyczna]] * [[Hierarchia Boole'owska]] | opis5 = Rodziny klas | spis5 = * [[DTIME]] * [[NTIME]] * [[DSPACE]] * [[NSPACE]] * [[PCP (klasa złożoności)|Dowód weryfikowalny probabilistycznie]] * [[Interaktywny system dowodowy]] | kategoria = informatyka | kategoria2 = podstawy matematyki