Хорошо известно, что набор языков, имеющих интерактивные системы доказательства с двумя доказательствами, в которых верификатор работает за полиномиальное время (MIP), является NEXP. Но известны ли пределы силы таких интерактивных доказательств, когда доказатели ограничены в силе? Например, что такое класс языков, которые допускают интерактивные доказательства с двумя доказательствами с помощью проверок за полиномиальное время?
Точнее, скажем, что на входе x я позволяю проверяющим произвольное время предварительного вычисления, но как только взаимодействие с верификатором начинается, они ограничиваются использованием полиномиального пространства (включая сохранение результатов любого предварительного вычисления) и полиномиального времени вычислить их ответы на вопрос проверяющего. Давайте также предположим, что эти пространственные и временные границы являются фиксированным полиномом по длине вопросов, которые будут отправлены верификатором (вместо длины x), чтобы исключить более тривиальное решение, в котором верификатор каким-то образом исчерпал бы пространство испытателя ограничено полиномиально большим количеством вопросов.
Понятно, что этого достаточно для NP. А как насчет PSPACE? Если бы было только ограниченное пространство, они могли бы сделать это, но что со временем? Есть ли интересные результаты в этом направлении?
Я также заинтересован в других ограничениях, которые можно рассмотреть на пруверах. Одним из них будет количество проверяющих и проверяющих коммуникацию, которые, я думаю, были тщательно изучены в контексте PCP. Каковы другие интересные ограничения?
Если два средства проверки ограничены двумя машинами BQP, которые не связываются друг с другом, но разделяют запутанность, в то время как верификатор находится в BPP, то эти два средства проверки могут проверить любой язык в BQP для классического верификатора с использованием универсального слепого квантового вычисления протокол Бродбента, Фицсимона и Кашефи. Этот протокол также использовался теми же авторами, что и строительный блок, для отображения QMIP = MIP * .
источник