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

Матеріал з Вікіпедії — вільної енциклопедії.

п о р Класи складності алгоритмів
Вважаються легкими	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
Ієрархії	Поліноміальна Гжегорчика
Теорія складності обчислень • Список алгоритмів