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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
<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>\Sigma_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p</tex> {{---}} <tex>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>.
+
где <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} = \{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>\Pi_{i} = \{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p</tex> {{---}} <tex>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>L</tex> — формальный язык <tex>,Q = \forall</tex> для <tex>i = 2k$-$1,</tex> <tex>Q = \exists</tex> для <tex>i = 2k</tex>.
 
}}
 
}}
  
Строка 48: Строка 48:
 
{{Теорема
 
{{Теорема
 
|statement = <tex>\Sigma_{i} = co\Pi_{i}</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/>
+
|proof = <tex>co\Pi_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p</tex> {{---}} <tex>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> очевидно равенство.
 
Из самого выражения для <tex>co\Pi_{i}</tex> очевидно равенство.
 
}}
 
}}
Строка 74: Строка 74:
 
Таким образом, для любого формального языка из <tex>PH</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>PH</tex> принадлежит <tex>PS</tex>.
 
Таким образом, для любого формального языка из <tex>PH</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>PH</tex> принадлежит <tex>PS</tex>.
 
}}
 
}}
 +
/tex>.
 +
|proof =

Версия 17:57, 13 апреля 2012

Классы Σ и Π

Определение:
[math]\Sigma_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p[/math] — [math]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[/math] — [math]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} \subset \Sigma_{i+1} \cap \Pi_{i+1}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]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}), \forall j |y_{j}| \le poly(|x|)[/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]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}), \forall j |y_{j}| \le poly(|x|)[/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[/math] — [math]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]

Класс PH

Определение:
[math]PH_{1} = {\bigcup \atop {k \in \mathbb{N}}} \Sigma_{i}[/math].

[math]PH_{2} = {\bigcup \atop {k \in \mathbb{N}}} \Pi_{i}[/math].

[math]PH_{3} = {\bigcup \atop {k \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})[/math].


Теорема:
Все три определения класса [math]PH[/math] эквивалентны, т.е. [math]PH_{1} = PH_{2} = PH_{3}[/math].
Доказательство:
[math]\triangleright[/math]

[math]\Sigma_{i} \subset \Pi_{i+1} \Rightarrow PH_{1} \subset PH_{2}[/math].
[math]\Pi_{i} \subset (\Sigma_{i+1} \cap \Pi_{i+1}) \subset (\Sigma_{i+1} \cup \Pi_{i+1}) \Rightarrow PH_{2} \subset PH_{3}[/math].
[math]\Pi_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Sigma_{i+1} \Rightarrow PH_{3} \subset PH_{1}[/math].

Т.о., [math]PH_{1} \subset PH_{2} \subset PH_{3} \subset PH_{1}[/math].
[math]\triangleleft[/math]
Теорема:
[math]PH \subset PS[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]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}), \forall j |y_{j}| \le poly(|x|)[/math].
То есть, для перебора всех возможных значений [math]y_{j}[/math] потребуется не более, чем [math]i \cdot poly(|x|)[/math] памяти. Заметим, что [math]i \cdot poly(|x|)[/math] тоже полином.

Таким образом, для любого формального языка из [math]PH[/math] существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из [math]PH[/math] принадлежит [math]PS[/math].
[math]\triangleleft[/math]

/tex>. |proof =

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Классы_PH,_Σ_и_Π&oldid=20574»