в пересчете на

15

Вероятностная система доказательств обычно называется ограничением M A , где Артур может использовать только f ( n ) случайных битов и может проверять только g ( n ) битов подтверждающий сертификат, присланный Мерлином (см. http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).пСп[е(N),грамм(N)]MAе(N)грамм(N)

Тем не менее, в 1990 году Бабай, Fortnow и Лунд доказано , что , поэтому его не в точности ограничение. Какие параметры ( f ( n ) , g ( n ) ) для которых P C P [ f ( n ) , g ( n )пСп[поLY(N),поLY(N)]знак равноNЕИкспе(N),грамм(N) ?пСп[е(N),грамм(N)]знак равноMA

красавица
источник

Ответы:

18

Если вы хотите переформулировать определение MA в терминах PCP, вам нужен другой параметр для PCP, а именно длина доказательства. MA явно совпадает с PCP с полиномиальной случайностью, полиномиальными запросами и доказательствами полиномиальной длины. Обычно длина доказательства в PCP не ограничена (то есть она ограничена только неявно случайностью и запросами), но этого недостаточно, чтобы переформулировать определение MA.

Если вы ищете некоторую характеристику вида MA = PCP ( q ( n ), r ( n )), которая не является просто повторением определения MA, то я не думаю, что какая-либо такая характеристика известна.

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

В соответствии с предположением твердости, а именно, что класс сложности , требует схемы экспоненциального размера, достаточно derandomize M A , так что М = Н Р . Фактически, дерандомизация заключается в том, чтобы показать, что B P P = P (см. Impagliazzo-Wigderson или Sudan-Trevisan-Vadhan). Но поскольку в M A верификатор является машиной B P P , мы можем заменить ее детерминированной машиной.Езнак равноDTяMЕ(2О(N))MAMAзнак равноNпВппзнак равнопMAВпп

Таким образом, по модулю этой твердости предположения, должны иметь точно такую же характеристику , как PCP N P . Сообщество сложности, похоже, твердо верит, что предположение о твердости также верно.MANп

Изменить: Вы также можете взглянуть на магистерскую диссертацию Энди Друкера: «Характеристика PCP для »: http://eccc.hpi-web.de/report/2010/019/ .AM

Импальяццо-Вигдерсон: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf

Судан-Тревизан-Вадхан: http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps

Генри Юн
источник
11

Цуёси Ито ответил на вопрос буквально, но я хотел прокомментировать семантику MA и PCP и то, как они различаются.

MA - это вероятностная версия NP, т. Е. Верификатор также использует много случайных битов.

В PCP мы можем ссылаться на «случайность» верификатора, но обычно случайность является логарифмической во время работы верификатора, то есть верификатор мог бы попробовать все возможные случайные строки сам по себе. Другими словами, эта «случайность» не дает верификатору никакой вычислительной мощности, в отличие от случая МА.

[Так для чего же эта «случайность»? Суть PCP в том, что для вероятностной проверки достаточно одного теста - с постоянным количеством запросов к доказательству - достаточно]

Приложение (после комментария Цуёси): В характеристиках PCP NP время выполнения верификатора можно сделать полулогарифмическим, и, аналогично, в характеристиках NEXP время выполнения верификатора является полиномиальным. Тем не менее, случайность в конструкциях PCP обычно используется только для выбора теста (в характеристиках NP, из поли-многих тестов и в характеристиках NEXP, из экспоненциально многих) и не помогает в вычислениях. Более того, в MA доказательство имеет полиномиальный размер, в то время как в характеристиках NEXP доказательство имеет экспоненциальный размер.

Дана Мошковиц
источник
Я согласен с тем, что мы даем верификатору только логарифмическую случайность в теореме PCP для NP, чтобы одна эта случайность не купила верификатору никакой вычислительной мощности. Однако кажется, что вы делаете более общее утверждение, чем это, заявляя, что «обычно случайность является логарифмической во время выполнения верификатора», что, я боюсь, является слишком общим, чтобы быть правдой. Обычно мы не позволяем верификатору тратить экспоненциальное время, даже если мы рассматриваем PCP (poly, poly) = NEXP (хотя это не меняет это равенство), и это кажется контрпримером к вашему утверждению.
Цуёси Ито
1
Спасибо за продолжение! Я думаю, что теперь я лучше понимаю, что вы имеете в виду, говоря, что МА и РСР используют случайность по-разному.
Цуёси Ито