Шаблон:Классы сложности

Материал из Википедии — свободной энциклопедии

Классы сложности алгоритмов
Считаются лёгкими	DLOGTIME^[англ.] AC⁰^[англ.] ACC⁰^[англ.] TC⁰^[англ.] L SL^[англ.] RL^[англ.] NL NC SC^[англ.] CC^[англ.] P P-complete^[англ.] ZPP RP BPP BQP EQP APX
Предполагаются сложными	UP^[англ.] NP NP-complete co-NP co-NP-complete AM^[англ.] MA^[англ.] QMA PH ⊕P^[англ.] PP #P #P-complete^[англ.] IP^[англ.] PSPACE PSPACE-complete^[англ.]
Считаются сложными	EXPTIME NEXPTIME^[англ.] EXPSPACE^[англ.] 2-EXPTIME^[англ.] ELEMENTARY^[англ.] R PR^[англ.] RE^[англ.] RE-complete^[англ.] Co-RE^[англ.] Co-RE-complete^[англ.] ALL^[англ.]