94
правки
Изменения
Нет описания правки
Полиномиальная иерархия - иерархия классов сложности, которая обобщает классы [[Класс P|P]], [[Класс NP|NP]] и [[Класс coNP|coNP]] до вычислений с оракулом.[[Файл:Ph_diagram.jpg|thumb|350px|Отношения классов полиномиальной иерархии]]
==Классы из полиномиальной иерархии==
Приведем некоторые соотношения между классами [[Классы Sigma_iи Pi_i|<texmath>\Sigma_i</texmath>]] и [[Классы Pi_i|<texmath>\Pi_i</texmath>]].
<tex>\Sigma_0 = P</tex><br>
<tex>\cup_{n=0}^{\infty} \Sigma_n = \cup_{n=0}^{\infty} \Pi_n = PH</tex>
===Связь языков из <math>\Sigma_i</math> и <math>\Pi_i</math>===
Если язык <tex>L</tex> принадлежит [[Классы Sigma_i|классу <texmath>\Sigma_i</texmath>]], то дополнение <tex>\overline{L}</tex> принадлежит [[Классы Sigma_i и Pi_i|классу <texmath>\Pi_i</texmath>]]
==Коллапс полиномиальной иерархии==
