Классы PH, Σ и Π

Материал из Викиконспекты
Версия от 13:50, 13 апреля 2012; Логунов Глеб (обсуждение | вклад) (Новая страница: «{{Определение |definition = <tex>\Sigma_{i}</tex> {{---}} <tex>\{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p - poly : \forall x \in L \Leftrightarrow \...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
[math]\Sigma_{i}[/math][math]\{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p - poly : \forall x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} \},[/math] где [math]L[/math] - формальный язык [math],Q = \exists[/math] для [math]i = 2k - 1,[/math] [math]Q = \forall[/math] для [math]i = 2k[/math].


Определение:
[math]\Pi_{i}[/math][math]\{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p - poly : \forall x \in L \Leftrightarrow \forall y_{1} \exists y_{2} \forall y_{3} \cdots Q y_{i} \},[/math] где [math]L[/math] - формальный язык [math],Q = \forall[/math] для [math]i = 2k - 1,[/math] [math]Q = \exists[/math] для [math]i = 2k[/math].