Интерактивные доказательства для уровней полиномиальной иерархии

33

Мы знаем, что если у вас есть машина PSPACE, она достаточно мощна, чтобы предоставить интерактивное доказательство любого уровня полиномиальной иерархии. (И если я правильно помню, все, что вам нужно, это #P.) Но предположим, что вы хотите предоставить интерактивное подтверждение членства на языке . Достаточно ли этого, чтобы иметь возможность решать проблемы в ? Является ли решение проблем в адекватным? В более общем смысле, если вы можете решить задачи или , для чего этого достаточно для генерации интерактивных доказательств всех языков в ? $\Sigma_2$ $\Sigma_2$ $\Sigma_5$ $\Sigma_k$ $\Pi_k$ $\Sigma_\ell$ $\Sigma_\ell$

Этот вопрос был вдохновлен этим вопросом об обмене стека теории .

cc.complexity-theory interactive-proofs Питер Шор
источник

Вас интересует только случай с одним прувером или вас интересует случай нескольких пруверов? Мне кажется, что очевидный способ атаковать это был бы через PCP, которые могли бы быть простыми для двух проверяющих, но, вероятно, не будут работать для одного проверяющего.

Джо Фицсимонс

1

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

Питер Шор

4

@Peter: Глядя на статью IP = PSPACE, кажется, что доказательство будет проходить с использованием

(который является полным для

), а не QBF, при условии, что у вас есть достаточно мощный инструмент для вычисления полиномиальных тождеств, возникающих из арифмитизация

. Я что-то пропустил?

{QBF}_{k}

$\mbox{QBF}_k$

Σ_{k}^{P}

$\Sigma^P_k$

{QBF}_{k}

$\mbox{QBF}_k$

Джо Фицсимонс

1

@ Джо, я не обдумал эту идею; это может сработать.

Питер Шор

2

Джо, может, тебе стоит опубликовать это как ответ

Суреш Венкат

25

Даже для предоставления IP для coNP, используя современные методы, нужно арифметизировать, то есть использовать подсчет, что означает, по существу, полную мощность #P. Я думаю, что любой более слабый прувер даже для coNP был бы очень интересным (в частности, подразумевал бы новую нерелятивистскую технику).

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

@ Питер: Ноам прав. Я цитирую следующие строки из здесь : ... основывая столкновения стойкого хэширование на наихудшей твердости НП за счетом сокращения черного ящика предполагает интерактивную систему доказательства для сотрудничества НП с расстойкой в BPP ^ NP ... Все известный (даже мульти-прувер) системы доказательства для co-NP требуют пруверов со сложностью #P ...

MS Dousti 27.10.10

В этом случае мой ответ, скорее всего, глупость. Спасибо за указание на это.

Джо Фицсимонс

На самом деле, это действительно интересно, учитывая, что интерактивному доказательству неизоморфизма графа нужен только доказатель с оракулом для этой проблемы. Это похоже на доказательство того, что либо GI очень очень слаб (как в P), либо границы для интерактивных доказательств уровней полиномиальной иерархии, вероятно, очень слабые.

Джо Фицсимонс

1

Я предполагаю, что несколько проверяющих, как известно, не помогают. Это верно?

Питер Шор

1

@Joe Доказательство для неизоморфизма графа является постоянным круглым публичным доказательством монет, таким образом, помещая его в класс AM (широко считается равным NP, и, следовательно, GI и GNI, как полагают, находятся в

). Это намного ниже, чем полиномиальное круглое доказательство, которое, как полагают, необходимо для доказательства членства в полных задачах coNP.

N P \cap c o N P

$NP \cap coNP$

Вооз Барак

21

Это известная (замечательная) открытая проблема, над которой я время от времени работал, но безуспешно.

Ави Вигдерсон и я упомянули эту проблему в нашей статье по алгебризации , где мы подняли вопрос о том, можно ли доказать сдерживание, такое как coNP ⊆ IP _NP , с помощью методов алгебрирования. (Здесь IP _NP обозначает IP с БПП верификатор и БПП ^НП расстойки.) Если (как я догадка) ответ нет, то , что не даст формальный повод , почему любой интерактивный протокол , как один Питер просит потребует не-релятивизации методы, которые выходят «за рамки» тех, которые используются для IP = PSPACE.

Аналогичный вопрос заключается в том, является ли BQP = IP _BQP , где IP _BQP означает IP с верификатором BPP и средством проверки BQP (квантового полиномиального времени). Этот вопрос также открыт - хотя недавний прорыв Бродбента, Фицсимона и Кашефи показал, что тесно связанное утверждение верно.

Скотт Ааронсон
источник

20

Да, вопрос о том, есть ли у coNP интерактивное доказательство, где средство проверки слабее, чем #P (скажем, polytime с доступом к NP oracle), является хорошо известным открытым вопросом. Следующая недавняя статья Хайтнера, Махмуди и Сяо обсуждает этот вопрос и показывает некоторые последствия предположения, что это невозможно сделать.

Боаз Барак
источник

11

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

$\mbox{QBF}_k$ $\Sigma^P_k$ $\mbox{QBF}_k$ $\Sigma^P_k$

Джо Фитцсимонс
источник

проблема уже возникает в доказательстве для coNP. Протокол проверки сумм имеет n раундов (по одному на каждую переменную). В каждом раунде проверяющий должен придумать коэффициенты полинома, который получается некоторой экспоненциально большой суммой. Я не знаю, как сделать это, используя меньше энергии, чем #P.

Вооз Барак

@ Боаз: Да, я думаю, что этот подход обречен на провал. Я думал, что видел вариант арифметизации, выполненный где-то таким образом, что полином принимает значения 1 или 0 только для входов 0 и 1. Если это так, похоже, вы могли бы использовать оракула для решения соответствующей проблемы. Опять же, я мог просто представить это!

Джо Фицсимонс

Интерактивные доказательства для уровней полиномиальной иерархии

Ответы: