Шаблон:Класи складності

п о р Класи складності алгоритмів

Вважаються легкими	P L NL AC NC P-повні BQP BPP RP ZPP APX

Припускаються складними	NP co-NP NP-повні NP-складні co-NP-повні UP #P (#P-повні) IP PSPACE (PSPACE-повні) R PP AM MA QMA

Вважаються складними	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH

Ієрархії	Поліноміальна Гжегорчика

Теорія складності обчислень • Список алгоритмів