108
правок
Изменения
Нет описания правки
|definition =
<tex>\mathrm{PCP}</tex>'''-системой''' (системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]], имеющая доступ к цепочке <tex>\pi \in \Sigma^{*} : |\pi| \le 2^{poly(|input|)}</tex> {{---}} доказательству, удовлетворяющая следующим свойствам:
* '''Полнота''': если <tex>x \in L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не меньше <tex>c(n)</tex> для некоторой <tex>\pi</tex>.,
* '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не больше <tex>s(n)</tex> для любой <tex>\pi</tex>.
}}
}
Проверим полноту и обоснованность:
* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1.;
* '''Обоснованность''': если графы изоморфны, то благодаря случайному выбору <tex>i</tex> вероятность ошибки не превышает <tex>{}^1/{}_2</tex>.
}}
