Классы PH, Σ и Π

Определение:

[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].