143
правки
Изменения
собственно PCP
}}
==Эквивалентность PCP-теоремы и NP-трудности задачи об аппроксимации==
{{Теорема
|id=pcp_th
|about=<tex>\mathrm{PCP}</tex> теорема
|statement=<tex>\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}</tex>
}}
{{Теорема
|statement=Существуют <tex>q \in \mathbb{N}, \rho \in (0, 1)</tex> такие, что задача <tex>\rho-GAPqCSP</tex> — <tex>\mathrm{NP}</tex>-трудная.
