Последствия содержащие

34

Многие считают, что . Однако мы только знаем, что находится на втором уровне полиномиальной иерархии, то есть . Шаг к показу состоит в том, чтобы сначала перевести его на первый уровень полиномиальной иерархии, то есть .BPP=PNPBPPBPPΣ2PΠ2PBPP=PBPPNP

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

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

Есть ли какие-нибудь интересные интересные последствия для ?BPPNP

Есть ли основания полагать, что доказательство сейчас недоступно (например, барьеры или другие аргументы)?BPPNP

Кава
источник
3
Ну, я не думаю, что известно, что, coRPNP

Ответы:

37

С одной стороны, доказательство будет легко означать, что , что уже означает, что ваше доказательство не может быть релятивизировано.BPPNPNEXPBPP

Но давайте посмотрим на что-то еще более слабое: . Если это так, то проверка полиномиальной идентичности для арифметических схем проводится в недетерминированное субэкспоненциальное время. Согласно Impagliazzo-Kabanets'04 , такой алгоритм подразумевает нижние границы схемы: либо у Permanent нет арифметических схем, либо .coRPNTIME[2no(1)]NEXPP/poly

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

Райан Уильямс
источник
12
Небольшое дополнение, если кому-то интересно: хотя мы с Ави и не думали делать это в нашей статье, я полагаю, что можно легко показать, адаптировав наши аргументы (например, для NEXP против P / poly), что любое доказательство BPP в NP должен был бы быть также неалгебрирующим.
Скотт Ааронсон
2
Скотт: Я не сомневаюсь, что это тоже правда!
Райан Уильямс
@RyanWilliams Применяется ли барьер естественных доказательств для BPP в NP? спрашивая об этом, потому что как можно было преодолеть барьер (если он вообще есть), чтобы показать сдерживание в ? Σ2
Т ....
2
Поскольку природные свойства обычно говорят только о барьерах против неоднородных (контурных) нижних границ, я не знаю, что они могли бы сказать о том, содержится ли BPP в NP.
Райан Уильямс
@RyanWilliams: «Постоянный не имеет многоразмерных арифметических схем» так же, как или он слабее? VNPVP
T ....