Изменения

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

Теоремы о коллапсе полиномиальной иерархии

55 байт добавлено, 09:05, 15 апреля 2012
м
Нет описания правки
<tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_1(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. Значит, <tex>L \in \Sigma_i</tex>. То есть <tex>\Sigma_i = \Sigma_{i+1}</tex>.
}}
 
== См. также ==
*[[Классы PH, Σ и Π]]
205
правок

Навигация