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

Полиномиальная иерархия - иерархия классов сложности, которая обобщает классы P, NP и coNP до вычислений с оракулом.

Если [math]\Sigma_n = \Sigma+{n+1}[/math] или [math]\Sigma_n = \Pi_n[/math], то по теоремам о коллапсе полиномиальной иерархии полиномиальная иерархия сжимается до уровня [math]n[/math]. То есть если [math]i \gt n[/math], то [math]\Sigma_i = \Sigma_n[/math]. Это означает, что равенство классов P и NP схлопывает полиномиальную иерархию.

Объединение всех классов полиномиальной иерархии называется классом PH.

Известно что PH является подмножеством PS, но о равенстве между этими классами ничего не известно.