Последствия

У меня есть часть попытки доказательства . Попытка доказательства состоит в сокращении Карпа из -полной задачи 3-REGULAR VERTEX COVER к SAT. $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P}$ $\oplus$

Учитывая кубический граф , сокращение выводит формулу CNF, имеющую оба следующих свойства: $G$ $F$

$F$ имеет самое большее удовлетворительное назначение. $1$
$F$ выполнимо тогда и только тогда, когда число покрытий вершин нечетно. $G$

Вопросов

Какими будут последствия ? Следствие, о котором я уже знаю, заключается в следующем: может быть приведен к посредством двустороннего рандомизированного сокращения. Другими словами, мы будем иметь (используя теорему Тоды, которая гласит, что , просто заменив на ). Я не знаю, было ли показано, что содержится в каком-то уровне Полиномиальной Иерархии: если да, дальнейшее последствие будет $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\mathbf{PH}$ $\mathbf{NP}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$ $\oplus\mathbf{P}$ $\mathbf{NP}$ $\mathbf{BPP}^{\mathbf{NP}}$ $i$ $\mathbf{PH}$ рушится до такого уровня . ~~Более того, в соответствии с широко принятыми допущениями дерандомизации (~~ ~~), полиномиальная иерархия будет разрушаться между первым и вторым уровнем, как мы бы имели~~ ~~(мне сказали, что это неправда, однако я не буду стирать эту строку, пока не полностью пойму, почему).~~ $i$ ~~$\mathbf{BPP} = \mathbf{P}$ $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$~~

Если я не ошибаюсь, вышеупомянутое сокращение фактически окажется больше, чем . Это докажет . Какими будут последствия , в дополнение к тем, которые уже подразумеваются ? Я не знаю точно, может ли еще больше удивить и без того удивительных последствий , и в какой степени. Интуитивно я полагаю, что это будет, и в значительной степени. $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$ $\oplus \mathbf{P} \subseteq \mathbf{UP}$ $\oplus \mathbf{P} \subseteq \mathbf{NP}$

cc.complexity-theory graph-theory complexity-classes sat counting-complexity Джорджио Камерани
источник

\oplus P

$\oplus\mathrm P$ замкнут относительно комплемента, и рандомизированное приведение PH к является множеством, следовательно, фактически подразумевает и . UP не имеет большого значения (см. Отсутствие чего-либо полезного в cstheory.stackexchange.com/questions/3887 ).

\oplus P

$\oplus\mathrm P$

\oplus P \subseteq N P

$\oplus\mathrm P\subseteq\mathrm{NP}$

P H = Σ_{2}^{P} = Π_{2}^{P} = A M \cap c o A M

$\mathrm{PH}=\Sigma^P_2=\Pi^P_2=\mathrm{AM}\cap\mathrm{coAM}$

P H \subseteq N P / p o l y \cap c o N P / p o l y

$\mathrm{PH}\subseteq\mathrm{NP/poly}\cap\mathrm{coNP/poly}$

Эмиль Йержабек

@ EmilJeřábek Спасибо за ваш интересный комментарий, я не знал, что последствия. Я знал вопрос, на который вы мне указали, однако я ожидал, что (а также ) удивителен хотя бы потому, что не имеет полных проблем. Интересно, что что-то широко предположительно ложное ( ), как известно, не имеет, если это правда, каких-либо шокирующих последствий. Вы могли бы рассмотреть возможность расширить свой комментарий в ответ ...

\oplus P \subseteq U P

$\oplus \mathbf{P}\subseteq\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

U P

$\mathbf{UP}$

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$

Джорджио Камерани

Нет, вы совершенно не правы. BPP = P говорит только о том, что каждый язык, который вычисляется на машине BPP, также можно вычислить на машине P. Он ничего не говорит о языках, которые можно вычислить на машине BPP с нетривиальным оракулом. По вашему неверному аргументу NP = P подразумевает для каждого , который, как мы знаем, является ложным, поэтому решается. И если на то пошло, ваш аргумент будет означать , так как существуют оракулов , для которых .

{N P}^{A} = P^{A}

$\mathrm{NP}^A=\mathrm P^A$

A

$A$

N P \neq P

$\mathrm{NP}\ne\mathrm P$

B P P \neq P

$\mathrm{BPP}\ne\mathrm P$

A

$A$

{B P P}^{A} \neq P^{A}

$\mathrm{BPP}^A\ne\mathrm P^A$

Эмиль Йержабек

@ Джорджио: Он только утверждает, что рассуждение, которое вы рассмотрели, не работает в этих обстоятельствах. Соответствующая часть: «Если машина, к которой я присоединяю оракула, хотя бы столь же мощна, то почему не должно следовать включение?». Он, кажется, не говорит, что само требование является ложным; просто ваша особая интуиция не работает. Мы пока не можем исключить, что вероятностные аспекты PPTM не могли получить больше пользы от этого оракула. Вероятностная TM имеет в своем распоряжении больше инструментов, но этот инструмент может не принести строгой выгоды без дополнительных инструментов (таких как оракул NP).

mdxn

Даже если предположить, что PRNG достаточно сильный, чтобы разрушить P и BPP, я не понимаю, почему это обязательно подразумевает BPP с оракулом NP и P с оракулом NP должны быть одинаковыми. Обычно PRNG имеют гарантию того, что ни одна схема полисайта не сможет отличить их выходные данные от действительно случайных битов. Но для машин оракула вам нужна гарантия на каждую схему полисайта с разрешенными воротами NP, и это сильнее. Impagliazzo-Wigderson действительно релятивизируется, но вам нужно усилить предположение о твердости ( eccc.hpi-web.de/report/1998/055/comment/1/download )

Сашо Николов

Последствия

Ответы: