Классы PH, Σ и Π

Классы Σ и Π

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

$\Sigma_{i} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{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})\},$ где $L$ — формальный язык $,Q = \exists$ для $i = 2k$-$1,$ $Q = \forall$ для $i = 2k$.

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

$\Pi_{i} = \{L \bigm| \exists R(x, y_{1},\cdots,y_{i}) \in \mathrm{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}) \},$ где $L$ — формальный язык $,Q = \forall$ для $i = 2k$-$1,$ $Q = \exists$ для $i = 2k$.

Соотношения между классами Σ и Π

Теорема:

$\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}$.

Доказательство:

$\triangleright$

Пусть $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|)$. Проверим, что $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})$. $R'(x,y_{1},\cdots,y_{i+1})$ { return $R(x,y_{1},\cdots,y_{i})$; } Проверим, что $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})$. $R''(x,y_{0},y_{1},\cdots,y_{i})$ { return $R(x,y_{1},\cdots,y_{i})$; } Таким образом, $\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}$.

$\triangleleft$

Теорема:

$\Sigma_{i} = \mathrm{co\Pi_{i}}$.

Доказательство:

$\triangleright$

$\mathrm{co\Pi_{i}} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{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})\}.$ Из самого выражения для $\mathrm{co\Pi_{i}}$ очевидно равенство.

$\triangleleft$

Пример Σ-полной задачи

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

{{{definition}}}

$\mathrm{QBF_{k}}$ — $\mathrm{\Sigma_{k}}$-полная задача (доказательство аналогично доказательству полноты TQBF.

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

{{{definition}}}

Аналогично предыдущей, $\mathrm{QBF^{Pi}_{k}}$ — $\mathrm{\Pi_{k}}$-полная задача.

Класс PH

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

$\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} \Sigma_{i}$.

Замечание: иногда удобнее пользоваться альтернативными определениями $\mathrm{PH}$. Например:

• $\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} \Pi_{i}$,
  
• $\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})$.

Теорема:

$\mathrm{PH} \subset \mathrm{PS}$.

Доказательство:

$\triangleright$

Пусть $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|)$. То есть, для перебора всех возможных значений $y_{j}$ потребуется не более, чем $i \cdot poly(|x|)$ памяти. Заметим, что $i \cdot poly(|x|)$ тоже полином. Таким образом, для любого формального языка из $\mathrm{PH}$ существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из $\mathrm{PH}$ принадлежит $\mathrm{PS}$.

$\triangleleft$