Пейзаж интерактивных систем доказательства

Мой первый вопрос: известна ли интерактивная характеристика системы доказательств для всех классических классов сложности. Я бы назвал P, NP, PSPACE, EXP, NEXP, EXPSPACE рекурсивными и рекурсивно перечислимыми функциями классическими (среди прочих). В частности, известна ли интерактивная характеристика системы доказательств для рекурсивных и рекурсивно перечислимых функций?

Я знаю только, что IP = PSPACE и MIP = NEXPTIME. Под «знать» подразумевается, что я понимаю определения объектов с обеих сторон равенства и, возможно, понимаю равенство.

Мой второй вопрос: есть ли графическое резюме различных типов интерактивных систем доказательства и классов сложности, которые они характеризуют.

В частности, я хотел бы сослаться на фигуру, похожую на картину Иммермана описания характеристик сложности .

cc.complexity-theory big-picture interactive-proofs Виджай Д
источник

Что ты уже знаешь?

Tsuyoshi Ito

В интерактивной системе доказательств имеется более одного параметра переменной: какова сила верификатора, какова сила средства проверки, какой вид (и объем) связи им разрешен, имеют ли они предварительно распределенную случайность, выполняет ли верификатор должен прочитать все сообщение от средства проверки или у него есть произвольный доступ к сообщению и т. д.

Робин Котари

Немного подумав, я не думаю, что смогу адекватно ответить на ваш вопрос, потому что интерактивная система доказательств является широкой темой в теории вычислительной сложности. Возможно, вы захотите проверить главу 9 « Вычислительная сложность: концептуальная перспектива » Гольдрайха или главы 8 и 11 « Вычислительная сложность: современный подход » Ароры и Барака.

Цуёси Ито

@VijayD: Да, это часть проблемы. В описательных характеристиках сложности есть одна переменная (логика), поэтому, когда вы поднимаетесь вверх от FO к SO, вы переходите от AC0 к PH и т. Д. В интерактивных системах доказательства есть так много переменных, что не ясно, что хороший пейзаж можно нарисовать.

Робин Котари

Я не уверен, что этот вопрос достаточно хорошо уточнен. Существует тривиальный ответ: каждый класс можно «охарактеризовать» как «интерактивное доказательство», когда проверяющий в основном не делает много, а верификатор достаточно силен. Интересная вещь о результатах IP = PSPACE и MIP = NEXP (и PCP [O (\ log n), O (1)] = NP) состоит в том, что верификатор является на удивление слабым.

Сашо Николов

Ответы:

Вы можете найти много характеристик (особенно на ограниченных в пространстве верификаторах) в известном обзоре Кондона: Сложность ограниченных в пространстве интерактивных систем доказательства .

Вот список некоторых из них:

, где 2pfa (верификатор) - двусторонний вероятностный конечный автомат. $\mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)}$
, где pfa (верификатор) - односторонний вероятностный конечный автомат, взаимодействующий с двумя доказателями. $\mathsf{R} = \mathsf{2IP(pfa)}$
. $\mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)}$
. $\mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)}$
. $\mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)}$
, и т. Д. $\mathsf{P} = \mathsf{AM(log\mbox{-}space)}$ $\mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)}$

Некоторые недавние (в основном квантовые) результаты:

поYakaryilmaz, где 2qcfa (верификатор) - двусторонний конечный автомат, имеющий квантовый регистр постоянного размера. $\mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)}$
поYakaryilmaz, где 2pca (первый верификатор) - двусторонний вероятностный конечный автомат с одним счетчиком, а 2qca (последний верификатор) - два квантовый конечный автомат с одним счетчиком. $\mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)}$
Ито, Кобаяши и Ватроус дали новую характеристику на основе квантовых интерактивных систем доказательства с двойным экспоненциально малым разрывом в вероятности принятия между случаями полноты и обоснованности. $\mathsf{EXP}$
поJain, Ji, Upadhyay и Watrous, где QIP - квантовое обобщение систем IP. $\mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)}$
$\mathsf{NP}$
$\mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)}$

Абузер Якарылмаз
источник

Благодарность! Это именно то, что я хотел. Я не знал, как улучшить свой вопрос, который был слишком расплывчатым для экспертов, и я рад, что вы поняли мои намерения.

Виджей Д

Ну, тогда почему бы вам не отметить это как лучший ответ?

Джем Сэй

Потому что кто знает, что принесет завтра? Я хотел бы через неделю или 10 дней после публикации решить.

Виджай Д

NP часто характеризуется как система доказательств, в которой проверяющий отправляет доказательство за полиномиальную длину детерминированному верификатору за полиномиальное время, и после этого взаимодействие отсутствует. Класс рекурсивно перечислимых языков можно охарактеризовать аналогичным образом, заменив «полином» на «конечный».

Кроме того, поскольку класс рекурсивных языков R является пересечением RE и coRE, вы можете охарактеризовать R как систему доказательств, в которой всемогущий испытатель может убедить проверяющего с конечным временем как в достоверности правильных утверждений, так и в недействительности ложные претензии.

Класс EXP имеет характеристику в терминах системы доказательств с «конкурирующими проверяющими», т. Е. Системы доказательств, в которой есть проверяющий, который пытается убедить верификатора в том, что утверждение истинно, и опровержитель, который пытается убедить верификатора в том, что иск ложный. Смотрите статью «Делать игры короткими» о Фейге и Килиане для более подробной информации.

Или меир
источник