Материал из Викиконспекты
|
|
| Строка 42: |
Строка 42: |
| | } | | } |
| | Т.о., <tex>\Pi_{i} \subset \Sigma_{i+1}, \Pi_{i} \subset \Pi_{i+1} \Rightarrow \Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>. | | Т.о., <tex>\Pi_{i} \subset \Sigma_{i+1}, \Pi_{i} \subset \Pi_{i+1} \Rightarrow \Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>. |
| | + | }} |
| | + | |
| | + | {{Теорема |
| | + | |statement = <tex>\Sigma_{i} = co\Pi_{i}</tex> |
| | + | |proof = <tex>co\Pi_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p - poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}</tex><br/> |
| | + | Из самого выражения для <tex>co\Pi_{i}</tex> очевидно равенство. |
| | }} | | }} |
Версия 15:03, 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] |
| Теорема: |
[math]\Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]\left]L \in \Pi_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \forall y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i})\right.[/math]
[math]? L \in \Pi_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \forall 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 \Sigma_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \exists y_{0} \forall 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]\Pi_{i} \subset \Sigma_{i+1}, \Pi_{i} \subset \Pi_{i+1} \Rightarrow \Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}[/math]. |
| [math]\triangleleft[/math] |
| Теорема: |
[math]\Sigma_{i} = co\Pi_{i}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]co\Pi_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p - poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}[/math]
Из самого выражения для [math]co\Pi_{i}[/math] очевидно равенство. |
| [math]\triangleleft[/math] |
