Algoritmien teoriassa kompleksisuusluokat ovat laskennallisia ongelmia, jotka ovat suunnilleen samat laskennallisen monimutkaisuuden suhteen. Tarkemmin sanottuna kompleksisuusluokat ovat predikaattijoukkoja ( funktioita , jotka ottavat syötteenä sanan ja palauttavat vastauksen 0 tai 1), jotka käyttävät suunnilleen saman määrän resursseja laskemiseen.
Jokaiselle luokalle on luokka tehtäviä, jotka ovat "vaikeimpia" kyseisellä luokalla. Tämä tarkoittaa, että mikä tahansa tehtävä luokasta pelkistyy sellaiseksi tehtäväksi, ja lisäksi itse tehtävä on luokassa. Tällaisia tehtäviä kutsutaan tietyn luokan valmiiksi tehtäviksi ( eng. -complete ). Tunnetuin täydellinen ongelma on NP-täydellinen ongelma .
Täydelliset tehtävät ovat kätevä työkalu luokka-asunnon todistamiseen. Riittää, että yksi tällainen ongelma antaa algoritmin, joka sen ratkaisee ja kuuluu pienempään luokkaan, ja yhtäläisyys todistetaan.
Jokainen kompleksisuusluokka (suunnassa) määritellään joukoksi predikaatteja, joilla on tiettyjä ominaisuuksia. Tyypillinen monimutkaisuusluokan määritelmä näyttää tältä:
Monimutkaisuusluokka X on joukko predikaatteja P(x) , jotka ovat laskettavissa Turingin koneilla ja käyttävät laskemiseen O (f(n)) -resurssia, missä n on sanan x pituus .Resurssit otetaan yleensä laskentaajaksi (Turingin koneen työjaksojen lukumäärä) tai työalueeksi (nauhalla käytön aikana käytettyjen solujen lukumäärä). Tietyn luokan predikaattien (eli sanajoukon, jolle predikaatti palauttaa 1) tunnistamien kielten sanotaan myös kuuluvan samaan luokkaan.
Lisäksi monia luokkia voidaan kuvata myös matemaattisen logiikan tai peliteorian avulla .
Luokat merkitään yleensä isoilla kirjaimilla. C -luokan komplementtia (eli kielten luokkaa, jonka komplementit kuuluvat C : hen) merkitään co-C .
Kaikki kompleksisuusluokat ovat hierarkkisessa suhteessa: jotkut sisältävät muita. Useimpien sulkeumien osalta ei kuitenkaan tiedetä, ovatko ne tiukkoja. Yksi tunnetuimmista avoimista ongelmista tällä alueella on luokkien P ja NP yhtäläisyys . Jos tämä oletus on oikea (mitä monet tiedemiehet epäilevät), oikealla näkyvä luokkahierarkia romahtaa voimakkaasti. Tällä hetkellä yleisin hypoteesi on , että hierarkia ei ole rappeutunut (eli kaikki luokat ovat erilaisia). Lisäksi tiedetään varmasti, että EXPSPACE ei ole sama kuin PSPACE-luokka .
Tarkastellaan funktiota f ja syötemerkkijonoa, jonka pituus on n . Sitten luokka DTIME (f(n)) määritellään determinististen Turingin koneiden hyväksymäksi kieliluokiksi, jotka lopettavat työnsä ajassa, joka ei ylitä f(n) . Luokka NTIME (f(n)) puolestaan määritellään ei- deterministisen Turingin koneen hyväksymäksi kieliluokiksi, joka suorittaa työnsä ajassa, joka ei ylitä f(n) . Huomaa, että näitä luokkia määritettäessä ei ole muistirajoituksia.
Samalla tavalla kuin aikahierarkia, otetaan käyttöön muistihierarkia. Luokka DSPACE (f(n)) tarkoittaa kielten luokkaa, jonka deterministiset Turingin koneet hyväksyvät käyttämällä enintään f(n) muistipaikkaa työnauhoilla. Luokka NSPACE (f(n)) määritellään kieliluokaksi, jonka epädeterministiset Turingin koneet hyväksyvät ja käyttävät enintään f (n) muistipaikkaa työnauhoilla. Näiden luokkien määrittelyssä ei ole aikarajoituksia.
Muut edellä tarkastellut vastaavat luokat määritellään samalla tavalla. Tässä käytetyt lyhenteet:
| Algoritmien monimutkaisuusluokat | |
|---|---|
| Kevyenä pidetty | |
| Taitaa olla vaikeaa | |
| Vaikeaksi pidetty |
|