PCP-система — различия между версиями
(Новая страница: «{{Определение |definition = PCP-системой(системой вероятностно проверяемых доказательств) с пол...») |
(нет различий)
|
Версия 14:49, 3 июня 2012
Определение: |
PCP-системой(системой вероятностно проверяемых доказательств) с полнотой вероятностная машина Тьюринга с полиномиальным временем работы, имеющая доступ к цепочке — доказательству, удовлетворяющая следующим свойствам:
| и обоснованностью над алфавитом для языка , где , называется пара —