Cílem studia složitosti výpočtů je rozdělit úlohy řešené na počítačích do několika kategorií (složitostních tříd) podle jejich časové a paměťové náročnosti. Cesta k tomu vede přes zdánlivě kontra-intuitivní výsledek, že čas výpočtu na Turingově stroji a spotřebu políček pásky je možné urychlit libovolnou konstantou.
Urychlení stroje a komprese pásky se dosahuje rozšířením páskové abecedy, kdy například na jedno políčko umístíme informace ze dvou původních. To v praxi odpovídá rozšíření délky operandů instrukce v mikroprocesoru. Jestliže instrukce pracuje např. s 64-bitovými operandy namísto 32-bitových, lze v jednom kroku zpracovat dvojnásobně více informace.
U prostorové složitosti lze takto neomezeně snižovat spotřebu políček pracovních pásek (když nepočítáme obsah vstupní a výstupní pásky). U časové složitosti požadujeme, aby stroj vždy přečetl celý obsah vstupní pásky, a proto nemůže vykonat méně kroků, než je délka vstupu.
Věta o urychlení nám říká, že například třída DTIME(nk) je totožná se všemi třídami DTIME(f(n)), kde f(n) je libovolný polynom k-tého stupně. Obdobný vztah platí i pro prostorovou složitost. Vidíme také, že násobení konstantou u složitostních tříd nehrají žádnou roli.
Pro rozdělení problémů na zvládnutelné, tj. řešitelé na počítači v rozumném čase (paměti), a nezvládnutelné budeme považovat za klíčové, zda výpočet probíhá v logaritmickém, polynomiálním či exponenciálním čase (prostoru). Tím dospějeme k definici základních složitostních tříd jako P, NP, LOGSPACE, PSPACE a dalších.
Z praktického hlediska jsou nejdůležitější třídy P, NP, PSPACE. Několik známých problémů z těchto tříd:
- Třída P
- veškeré vyhledávací a třídicí algoritmy (v poli, v souborech a v databázích)
- řada grafových algoritmů (hledání [nejkratších] cest mezi dvěma vrcholy, souvislost grafu, planarita grafu a další - aplikace v sítích všeho druhu, jízdní řády, doprava...)
- vyhledávání vzorku v textu s případnými mutacemi (aplikace: antivirová analýza s pomocí virové databáze)
- test na prvočíselnost, nalezení největšího společného dělitele (aplikace: šifrování)
- lineární programování (jednoduché optimalizační problémy s lineární účelovou funkcí a omezujícími podmínkami)
- příslušnost slova do regulárního nebo bezkontextového jazyka (aplikace: kompilátory)
- LZW kompresní algoritmus a další (aplikace: gzip, rar...)
- Třída NP
- problém obchodního cestujícího a jeho aplikace v dopravních problémech
- mnoho dalších grafových problémů (k-klika, k-nezávislá podmnožina, vrcholové barvení...)
- velká většina optimalizačních problémů (plnění batohu, vytěžování vozidel, optimalizace výroby, problém čínského pošťáka, všechny problémy kvadratického programování...)
- nejdelší společné podslovo v množině slov (aplikace: analýza DNA, proteinů)
- mnohé hry jako sudoku,tetris, Rubikova kostka...
- Třída PSPACE
- splnitelnost výrokové formule s kvantifikátory
- příslušnost slova do kontextového jazyka (aplikace: analýza přirozených jazyků)
- řada problémů automatického plánování a rozvrhování, např. nalezení nejjednoduššího plánu
- řada grafových problémů, např. týkajících se routingu na Internetu
- mnohé hry jako dáma, piškvorky, Super Mario Bros...