Односторонние ошибки в вероятностных системах доказательств

10

В большинстве вероятностных систем доказательства (например, теорема PCP) вероятности ошибок обычно определяются на стороне ложноположительных значений, т. Е. Типичное определение может выглядеть так: если то верификатор всегда принимает, но в другом случае вероятность отклонения составляет не менее 1/2.xL

Есть ли проблема в том, чтобы допустить ошибку на другой стороне? Это означает, что верификатор всегда отклоняет, когда он должен, и делает только постоянную ошибку, когда ему нужно принять. Другая очевидная возможность - допустить ошибку с обеих сторон. Будут ли эти определения эквивалентны тем, которые обычно даются? Или они ведут себя по-другому? Или в этом отношении есть подлинная проблема в разрешении ошибок на другой стороне.?

Арнаб
источник
Почему отрицательный голос? Некоторые РСР не имеют идеальной полноты. С другой стороны, есть некоторые сокращения с идеальным звучанием, но не с совершенной полнотой («Свободные биты и т. Д.», Bellare + Goldreich + Sudan, стр. 21, последний абзац).
Юваль Фильмус
@Yuval Filmus: Есть много версий упомянутой вами статьи. На какую версию вы ссылаетесь?
Цуёси Ито
Большое спасибо вам обоим за ответы. Я предполагаю, что отрицательный голос произошел из-за ощущения, что это не вопрос исследования. Это не так. В любом случае, я даже не могу подтвердить ответ своей оценкой репутации, которая сегодня даже снизилась :)
Арнаб
@TsuyoshiIto В версии 2 она находится внизу страницы 22 (страница 24 файла).
Юваль Фильмус
1
Не имею представления. Я просто погуглил "идеальную устойчивость".
Юваль Фильмус

Ответы:

12

Допустимая ошибка полноты не имеет проблем, и ее часто рассматривают. Вот несколько указателей .

С другой стороны, вообще говоря, запрещение ошибки достоверности значительно снижает мощность модели.

В случае интерактивных систем доказательства, запрещение ошибки достоверности делает взаимодействие бесполезным, за исключением односторонней связи от проверяющего к верификатору; то есть IP с безупречной прочностью равен NP. Это можно показать, рассматривая NP-машину, которая угадывает случайные биты верификатора и стенограмму взаимодействия, которая заставляет верификатор принять [FGMSZ89].

В случае систем вероятностно проверяемого доказательства (PCP) те же рассуждения показывают, что требование идеальной надежности делает случайность бесполезной для выбора местоположений для запроса. Точнее, можно показать, что PCP ( r ( n ), q ( n )) с полнотой c ( n ) и безупречностью (даже с адаптивными запросами) равен классу C задач решения A = ( A да , А нет ) для которого существует язык B ⊆ {0,1} * × {0,1} * × {0,1} * в P такой, что

  • если xA да , то Pr y ∈ {0,1} r ( n ) [∃ z ∈ {0,1} q ( n ) такое, что ( x , y , z ) ∈ B ] ≥ c ( n ), а также
  • если xA нет , то ∀ y ∈ {0,1} r ( n )z ∈ {0,1} q ( n ) , ( x , y , z ) ∉ B ,

где n = | х | (Обратите внимание, что в определении класса C случай да не требует подготовки целого сертификата до того, как верификатор выберет случайную строку y , в отличие от обычного определения системы PCP. Сертификат может быть подготовлен после знания y , и нужна только запрашиваемая часть сертификата, поэтому длина z равна q ( n ). В сочетании с прямыми нижними границами это подразумевает следующее:

  • PCP (бревно, бревно) с идеальной стойкостью = P.
  • PCP (poly, log) с безупречной прочностью = RP .
  • PCP (поли, поли) с идеальной стойкостью = NP.

Сравнивая их с теоремами 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

Цуёси Ито
источник