Полиномиальная иерархия/Задачи/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>
+

Версия 01:39, 26 декабря 2014