Az algoritmusok elméletében a komplexitási osztályok olyan számítási problémák halmazai, amelyek számítási komplexitása megközelítőleg azonos. Szűkebb értelemben a komplexitási osztályok predikátumok halmazai ( függvények , amelyek bemenetként egy szót vesznek fel, és 0 vagy 1 választ adnak vissza), amelyek megközelítőleg ugyanannyi erőforrást használnak a számításhoz.
Minden osztályhoz tartozik egy olyan feladatkategória, amely az adott osztályban a "legnehezebb". Ez azt jelenti, hogy az osztályból származó bármely feladat ilyen feladattá redukálódik, ráadásul maga a feladat is az osztályban rejlik. Az ilyen feladatokat egy adott osztály esetében teljes feladatoknak ( eng. -complete ) nevezzük . A legismertebb teljes probléma az NP-teljes probléma .
A komplett feladatok kényelmes eszközt jelentenek az osztályegyenlőség bizonyítására. Elég, ha egy ilyen feladathoz megadunk egy kisebb osztályba tartozó algoritmust, amely ezt megoldja, és az egyenlőség bebizonyosodik.
Minden összetettségi osztály (szűk értelemben) predikátumok halmazaként van meghatározva, amelyek bizonyos tulajdonságokkal rendelkeznek. A komplexitási osztály tipikus meghatározása így néz ki:
Az X komplexitási osztály P(x) predikátumok halmaza, amelyek Turing-gépeken kiszámíthatók, és egy O (f(n)) erőforrást használnak a számításhoz, ahol n az x szó hossza .Az erőforrásokat általában számítási időnek (a Turing-gép munkaciklusainak száma) vagy munkaterületnek (a szalagon a működés során felhasznált cellák száma) veszik. Azok a nyelvek, amelyeket egy bizonyos osztály predikátumai ismernek fel (vagyis azon szavak halmaza, amelyekre az állítmány 1-et ad vissza), szintén ugyanabba az osztályba tartoznak.
Ezenkívül sok osztály leírható matematikai logika vagy játékelmélet szempontjából is .
Az osztályokat általában nagybetűkkel jelöljük. A C osztály kiegészítését (vagyis azon nyelvek osztályát, amelyek komplementerei a C-hez tartoznak ) co-C- nek jelöljük .
Valamennyi komplexitási osztály hierarchikus viszonyban áll: némelyik másokat is tartalmaz. A legtöbb zárvány esetében azonban nem tudni, hogy szigorúak-e. Az egyik leghíresebb nyitott probléma ezen a területen a P és NP osztályok egyenlősége . Ha ez a feltevés helyes (amiben sok tudós kételkedik), akkor a jobb oldalon látható osztályhierarchia erősen összeomlik. Jelenleg az a leggyakoribb hipotézis , hogy a hierarchia nem degenerált (azaz minden osztály más). Ezenkívül biztosan ismert, hogy az EXPSPACE nem egyenlő a PSPACE osztállyal .
Tekintsünk egy f függvényt és egy n hosszúságú bemeneti karakterláncot . Ekkor a DTIME (f(n)) osztályt a determinisztikus Turing-gépek által elfogadott nyelvek osztályaként definiáljuk, amelyek f(n) -nél nem nagyobb időben fejezik be a munkájukat . Az NTIME (f(n)) osztályt pedig úgy definiáljuk, mint a nem determinisztikus Turing-gép által elfogadott nyelvek osztályát, amely az f (n)-nél nem nagyobb időben fejezi be a munkáját . Vegye figyelembe, hogy ezen osztályok meghatározásakor nincsenek memóriakorlátozások.
Az időhierarchiához hasonlóan egy memóriahierarchiát vezetünk be. A DSPACE (f(n)) osztály a munkaszalagokon legfeljebb f(n) memóriahelyet használó determinisztikus Turing-gépek által elfogadott nyelvek osztályát jelöli . Az NSPACE (f(n)) osztály a nem determinisztikus Turing-gépek által elfogadott nyelvek olyan osztálya, amely a munkaszalagokon legfeljebb f(n) memóriahelyet használ. Ezen osztályok meghatározásakor nincs időkorlát.
A fentiekben tárgyalt többi hasonló osztály is hasonlóan van meghatározva. Íme a használt rövidítések:
| Algoritmusok összetettségi osztályai | |
|---|---|
| Fénynek tekinthető | |
| Állítólag nehéz | |
| Nehéznek tartott |
|