Изменения
Нет описания правки
По нашему предположению для задачи 3SAT существует верифаер <tex>V</tex> с доказательством <tex>\pi</tex> и обращается он к нему <tex>q</tex> раз, а случайной лентой пользуется <tex>clog(n)</tex> раз.
Теперь для любого входа <tex>x \in \{0, 1\}^n</tex> и случайной ленты <tex>r \in \{0, 1\}^{clog(n)}</tex> определим функцию <tex>V_{x, r}</tex> такую, что для доказательства — <tex>\pi</tex> возвращает 1, если верифаер принимает доказательство <tex>\pi</tex>, имея на входе <tex>x</tex> и ленту <tex>r</tex>. Получается что набор <tex>\varphi={V_{x, r}}</tex> для всех <tex>x</tex> и <tex>r</tex> является qCSP полиномиального размера. Так как верифаер работает за полиномиальное время, то <tex>x</tex> сводится к <tex>\varphi</tex> за полиномиальное время. И если <tex>x \in</tex> 3SAT, то <tex>val(\varphi) = 1</tex>, и <tex>x \not\in</tex> 3SAT, то <tex>val(\varphi) \leq \frac{1}{2}</tex>.
}}
