Полиномиальная иерархия/Задачи/compliment-in-ph — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
</latex>
 
</latex>
  
[[Category:Нерешенные задачи]]
+
[[Category:На проверку]]
 +
<latex>
 +
\\
 +
 
 +
\\Из определения \Sigma^p_k :
 +
\\$L \in \Sigma^p_k  \iff  \exists$ \ полином p; $\ \exists$ \ полиномиально проверяемый предикат R такой, что
 +
\\ x \in L \iff \exists y_1 \in \{0,1\}^{p(|x|)}, \forall y_2 \in \{0,1\}^{p(|x|)}, ..., y_k, \ $R(x, y_1, ..., y_k)=1; \ (1)$
 +
 
 +
\\Из определения \Pi^p_k :
 +
\\L' $\in \Pi^p_k  \iff  \exists$ \ полином p; $\ \exists$ \ полиномиально проверяемый предикат R' такой, что
 +
\\ x \in L'\iff\forall y_1 \in \{0,1\}^{p(|x|)}, \exists y_2 \in \{0,1\}^{p(|x|)}, ..., y_k, \ $R'(x, y_1, ..., y_k)=1; \ (2)$
 +
 
 +
\\Из отрицании (1), получаем
 +
\\x \in \{0,1\}^*\setminus L \iff \forall y_1 \in \{0,1\}^{p(|x|)}, \exists y_2 \in \{0,1\}^{p(|x|)}, ..., y_k, \ $R(x, y_1, ..., y_k)=0$;
 +
\ а это \ $\iff \ \{0,1\}^*\setminus L \in \Pi^p_k$ .(из определения (2))
 +
 
 +
</latex>

Версия 16:58, 18 декабря 2014