|
|
| (не показано 15 промежуточных версий 2 участников) |
| Строка 6: |
Строка 6: |
| | </latex> | | </latex> |
| | | | |
| − | [[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>
| + | |