В большинстве вероятностных систем доказательства (например, теорема PCP) вероятности ошибок обычно определяются на стороне ложноположительных значений, т. Е. Типичное определение может выглядеть так: если то верификатор всегда принимает, но в другом случае вероятность отклонения составляет не менее 1/2.
Есть ли проблема в том, чтобы допустить ошибку на другой стороне? Это означает, что верификатор всегда отклоняет, когда он должен, и делает только постоянную ошибку, когда ему нужно принять. Другая очевидная возможность - допустить ошибку с обеих сторон. Будут ли эти определения эквивалентны тем, которые обычно даются? Или они ведут себя по-другому? Или в этом отношении есть подлинная проблема в разрешении ошибок на другой стороне.?
Ответы:
Допустимая ошибка полноты не имеет проблем, и ее часто рассматривают. Вот несколько указателей .
С другой стороны, вообще говоря, запрещение ошибки достоверности значительно снижает мощность модели.
В случае интерактивных систем доказательства, запрещение ошибки достоверности делает взаимодействие бесполезным, за исключением односторонней связи от проверяющего к верификатору; то есть IP с безупречной прочностью равен NP. Это можно показать, рассматривая NP-машину, которая угадывает случайные биты верификатора и стенограмму взаимодействия, которая заставляет верификатор принять [FGMSZ89].
В случае систем вероятностно проверяемого доказательства (PCP) те же рассуждения показывают, что требование идеальной надежности делает случайность бесполезной для выбора местоположений для запроса. Точнее, можно показать, что PCP ( r ( n ), q ( n )) с полнотой c ( n ) и безупречностью (даже с адаптивными запросами) равен классу C задач решения A = ( A да , А нет ) для которого существует язык B ⊆ {0,1} * × {0,1} * × {0,1} * в P такой, что
где n = | х | (Обратите внимание, что в определении класса C случай да не требует подготовки целого сертификата до того, как верификатор выберет случайную строку y , в отличие от обычного определения системы PCP. Сертификат может быть подготовлен после знания y , и нужна только запрашиваемая часть сертификата, поэтому длина z равна q ( n ). В сочетании с прямыми нижними границами это подразумевает следующее:
Сравнивая их с теоремами PCP, PCP (log, O (1)) = NP и PCP (poly, O (1)) = NEXP, мы видим, что требование идеальной надежности имеет огромное влияние.
[FGMSZ89] Мартин Фюрер, Одед Голдрайх, Ишай Мансур, Майкл Сипсер и Статис Закос. О полноте и надежности в интерактивных системах доказательств. В Случайности и Вычислении , vol. 5 достижений в области компьютерных исследований , с. 429–442, 1989 г. http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps
источник