Классы PH, Σ и Π — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = <tex>\Sigma_{i}</tex> {{---}} <tex>\{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p - poly : \forall x \in L \Leftrightarrow \...»)
 
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\Sigma_{i}</tex> {{---}} <tex>\{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} \},</tex> где <tex>L</tex> - формальный язык <tex>,Q = \exists</tex> для <tex>i = 2k - 1,</tex> <tex>Q = \forall</tex> для <tex>i = 2k</tex>.
+
<tex>\Sigma_{i} = \{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} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\},</tex><br/>
 +
где <tex>L</tex> - формальный язык <tex>,Q = \exists</tex> для <tex>i = 2k-1,</tex> <tex>Q = \forall</tex> для <tex>i = 2k</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\Pi_{i}</tex> {{---}} <tex>\{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} \},</tex> где <tex>L</tex> - формальный язык <tex>,Q = \forall</tex> для <tex>i = 2k - 1,</tex> <tex>Q = \exists</tex> для <tex>i = 2k</tex>.
+
<tex>\Pi_{i} = \{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} : \forall j |y_{j}|~\le~p(|x|), R(x, y_{1}, \cdots, y_{i}) \},</tex><br/>
 +
где <tex>L</tex> - формальный язык <tex>,Q = \forall</tex> для <tex>i = 2k - 1,</tex> <tex>Q = \exists</tex> для <tex>i = 2k</tex>.
 +
}}
 +
 
 +
==Взаимоотношения между классами <tex>\Sigma_{i}</tex> и <tex>\Pi_{i}</tex>==
 +
{{Теорема
 +
|statement = <tex>\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>
 +
|proof = <tex>\left]L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i})\right.</tex><br/>
 +
<tex>? L \in \Sigma_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>
 +
<br/>
 +
  <tex>R'(x,y_{1},\cdots,y_{i+1})</tex> {
 +
    return <tex>R(x,y_{1},\cdots,y_{i})</tex>
 +
  }
 +
<tex>? L \in \Pi_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \forall y_{0} \exists y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>
 +
<br/>
 +
  <tex>R''(x,y_{0},y_{1},\cdots,y_{i})</tex> {
 +
    return <tex>R(x,y_{1},\cdots,y_{i})</tex>
 +
  }
 +
Т.о., <tex>\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.
 
}}
 
}}

Версия 14:47, 13 апреля 2012

Определение:
[math]\Sigma_{i} = \{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} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,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} = \{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} : \forall j |y_{j}|~\le~p(|x|), R(x, y_{1}, \cdots, y_{i}) \},[/math]
где [math]L[/math] - формальный язык [math],Q = \forall[/math] для [math]i = 2k - 1,[/math] [math]Q = \exists[/math] для [math]i = 2k[/math].


Взаимоотношения между классами [math]\Sigma_{i}[/math] и [math]\Pi_{i}[/math]

Теорема:
[math]\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}[/math]
Доказательство:
[math]\triangleright[/math]

[math]\left]L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i})\right.[/math]
[math]? L \in \Sigma_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})[/math]

 [math]R'(x,y_{1},\cdots,y_{i+1})[/math] {
   return [math]R(x,y_{1},\cdots,y_{i})[/math]
 }

[math]? L \in \Pi_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \forall y_{0} \exists y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})[/math]

 [math]R''(x,y_{0},y_{1},\cdots,y_{i})[/math] {
   return [math]R(x,y_{1},\cdots,y_{i})[/math]
 }
Т.о., [math]\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}[/math].
[math]\triangleleft[/math]