Изменения

Перейти к: навигация, поиск

Полиномиальная иерархия

5 байт добавлено, 23:11, 29 марта 2021
Нет описания правки
==Классы из полиномиальной иерархии==
Приведем некоторые соотношения между классами [[Классы Sigma_i Sigma_j и Pi_i|<math>\Sigma_i</math> и <math>\Pi_i</math>]].
<tex>\Sigma_0 = P</tex><br>
===Связь языков из <math>\Sigma_i</math> и <math>\Pi_i</math>===
Если язык <tex>L</tex> принадлежит [[Классы Sigma_i|классу <math>\Sigma_i</math>]], то дополнение <tex>\overline{L}</tex> не принадлежит [[Классы Sigma_i и Pi_i|классу <math>\Pi_i</math>]]
==Коллапс полиномиальной иерархии==
Анонимный участник

Навигация