Полиномиальная иерархия/Задачи/compliment-in-ph — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Larisa (обсуждение | вклад) |
||
| Строка 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