МИП с эффективными пруверами

17

Хорошо известно, что набор языков, имеющих интерактивные системы доказательства с двумя доказательствами, в которых верификатор работает за полиномиальное время (MIP), является NEXP. Но известны ли пределы силы таких интерактивных доказательств, когда доказатели ограничены в силе? Например, что такое класс языков, которые допускают интерактивные доказательства с двумя доказательствами с помощью проверок за полиномиальное время?

Точнее, скажем, что на входе x я позволяю проверяющим произвольное время предварительного вычисления, но как только взаимодействие с верификатором начинается, они ограничиваются использованием полиномиального пространства (включая сохранение результатов любого предварительного вычисления) и полиномиального времени вычислить их ответы на вопрос проверяющего. Давайте также предположим, что эти пространственные и временные границы являются фиксированным полиномом по длине вопросов, которые будут отправлены верификатором (вместо длины x), чтобы исключить более тривиальное решение, в котором верификатор каким-то образом исчерпал бы пространство испытателя ограничено полиномиально большим количеством вопросов.

Понятно, что этого достаточно для NP. А как насчет PSPACE? Если бы было только ограниченное пространство, они могли бы сделать это, но что со временем? Есть ли интересные результаты в этом направлении?

Я также заинтересован в других ограничениях, которые можно рассмотреть на пруверах. Одним из них будет количество проверяющих и проверяющих коммуникацию, которые, я думаю, были тщательно изучены в контексте PCP. Каковы другие интересные ограничения?

Томас
источник

Ответы:

17

Похоже, этот класс будет именно МА. Свидетелем могут быть результаты предварительной обработки (которая имеет полиномиальный размер). Процедура вероятностной проверки должна была бы затем симулировать протокол, включая множественные проверяющие (которые имеют полиномиальное время с учетом результатов предварительной обработки).

Рассел Импальяццо

Рассел Импальяццо
источник
Хороший вопрос, спасибо. В более общем плане мне было интересно, каким образом несколько проверяющих могут доказать языки, которые находятся за пределами их временной привязки T (по модулю этапа предварительной обработки), к верификатору poly-time, и ваш ответ показывает, что это никогда не будет больше, чем соответствующий MA (T), с T-временным верификатором. Но как это сравнить с каким-то классом верификатора поли-времени? Скажем, если проверяющим теперь разрешено быть PSPACE, они все равно могут доказать NEXP. Могут ли они быть более ограниченными и все же доказать то же самое?
Томас
2

Если два средства проверки ограничены двумя машинами BQP, которые не связываются друг с другом, но разделяют запутанность, в то время как верификатор находится в BPP, то эти два средства проверки могут проверить любой язык в BQP для классического верификатора с использованием универсального слепого квантового вычисления протокол Бродбента, Фицсимона и Кашефи. Этот протокол также использовался теми же авторами, что и строительный блок, для отображения QMIP = MIP * .

Мартин Шварц
источник
1
Спасибо Мартин, я не хотел упоминать мою собственную работу.
Джо Фицсимонс