Диаграмма классов сложности

Материал из свободной русской энциклопедии «Традиция»
Перейти к навигации Перейти к поиску

Диаграмма представляет отношения между основными классами сложности. Отношения вложенности обозначены «лапками», а эквивалентность — жирными линиями. Диаграмма гипертекстовая — то есть «кликая» на вершину некоторого класса, попадаешь на его определение.

Вообще, сейчас насчитывается не менее четырехсот различных классов сложности, например Зоопарк Классов Сложности упоминает о 442 классах.

G P P ZPP ZPP P->ZPP in PCP(log,q=2) PCP(log,q=2) P->PCP(log,q=2) equal NP NP PP PP NP->PP in PCP(log,1) PCP(log,1) NP->PCP(log,1) equal PCP(0,poly) PCP(0,poly) NP->PCP(0,poly) equal coNP coNP coNP->PP in BPP BPP ZPP->BPP in RP RP ZPP->RP in coRP coRP ZPP->coRP in BPP->PP in PSPACE PSPACE PP->PSPACE in NEXP NEXP PP->NEXP in RP->NP in RP->BPP in coRP->coNP in coRP->BPP in PCP(poly,0) PCP(poly,0) coRP->PCP(poly,0) equal PCP(log,log) PCP(log,log) PCP(log,1)->PCP(log,log) in PCP(log,1)->PCP(log,log) equal PCP(poly,poly) PCP(poly,poly) PCP(0,poly)->PCP(poly,poly) in PCP(poly,0)->PCP(poly,poly) in PCP(poly,poly)->NEXP equal PCP(log,log)->PCP(poly,poly) in PCP(log,q=2)->PCP(log,1) in


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.

Источник — https://traditio.wiki/w/index.php?title=Диаграмма_классов_сложности&oldid=848359