против

Центральная проблема теории сложности, возможно, против .Н $P$$NP$

Однако, поскольку Природа является квантовой, представляется более естественным рассмотреть классы (т. Е. Задачи решения, решаемые квантовым компьютером за полиномиальное время с вероятностью ошибки не более 1/3 для всех случаев) и (квантовый эквивалент из ) вместо этого.Q M A N $BQP$$QMA$$NP$

Мои вопросы:

1) Будет ли решение проблемы против дать решение против ?N P B Q P Q M $P$$NP$$BQP$$QMA$

2) Применимы ли три барьера релятивизации, естественных доказательств и алгебризации к проблеме против ?Q M $BQP$$QMA$

1) Никаких последствий не известно ни в одном направлении. Мы знаем, что P = NP подразумевает P = PH. Но мы не знаем, есть ли BQP и QMA в PH, поэтому, возможно, P мог бы равняться NP, но BQP и QMA все равно не будут разрушаться. (С другой стороны, обратите внимание, что QMA⊆PP⊆P ^#P , поэтому, безусловно, P = P ^#P подразумевает BQP = QMA.) Чтобы показать, что BQP = QMA подразумевает P = NP, кажется еще более безнадежным в нынешнем состоянии знаний ,

2) Безусловно, все три барьера с полной силой применяются к BQP против QMA (и даже к «более легкой» проблеме доказательства P ≠ PSPACE). Во-первых, относительно оракула PSPACE (или даже низкоуровневого расширения оракула PSPACE), мы имеем

P = NP = BQP = QMA = PSPACE,

поэтому, безусловно, для разделения любого из этих классов понадобятся нерелятивизирующие и неалгебрирующие методы. Во-вторых, чтобы получить естественный барьер доказательства для размещения материала вне BQP, все, что вам нужно, это семейство псевдослучайных функций, вычислимое в BQP, что формально более слабое требование, чем семейство псевдослучайных функций, вычислимое в P.

Приложение: Позвольте мне сказать кое-что о «метаквесте», о котором вы не спрашивали, но намекали на то, почему люди все еще фокусируются на P против NP, даже если мы считаем, что Природа является квантовой. Лично я всегда рассматривал P против NP как не что иное, как «флагман» для целого ряда барьерных вопросов в теории сложности (P против PSPACE, P против BQP, NP против coNP, NP против BQP, существование односторонних функций и т.д.), нииз которых мы знаем, как ответить, и все они связаны в том смысле, что любой прорыв с одним из них, скорее всего, приведет к прорыву с другими (даже если у нас нет формальных последствий между вопросами, которые во многих случаях мы делать). P против NP по своей природе не является более фундаментальным, чем любой другой - но если нам нужно выбрать один вопрос, который послужит детищем для сложности, то это хороший выбор.