Полиномиальная иерархия
Версия от 07:05, 31 марта 2021; 85.93.60.102 (обсуждение) (Отмена правки 80739, сделанной 46.242.10.153 (обсуждение))
Полиномиальная иерархия - иерархия классов сложности, которая обобщает классы P, NP и coNP до вычислений с оракулом.
Содержание
Классы из полиномиальной иерархии
Приведем некоторые соотношения между классами . и
Связь языков из и
Если язык классу , то дополнение принадлежит классу
принадлежитКоллапс полиномиальной иерархии
Если теоремам о коллапсе полиномиальной иерархии полиномиальная иерархия сжимается до уровня . То есть если , то . Это означает, что равенство классов P и NP схлопывает полиномиальную иерархию.
или , то поОбъединение классов полиномиальной иерархии
Объединение всех классов полиномиальной иерархии называется классом PH.
Известно что PH является подмножеством PS, но о равенстве между этими классами ничего не известно.