Konsekwencje

Mam część próbnej próby $\oplus \mathbf{P} \subseteq \mathbf{NP}$ . Próba dowodowa polega na zmniejszeniu karpu z $\oplus \mathbf{P}$ -kompletny problem $\oplus$ 3-REGULARNA POKRYWA VERTEX do SAT.

Biorąc pod uwagę sześcienny wykres $G$ , redukcja generuje wzór CNF $F$ posiadający obie następujące właściwości:

$F$ ma co najwyżej $1$ spełniające zadanie.
$F$ jest zadowalający tylko i tylko wtedy, gdy liczba pokryw wierzchołków wynosi $G$ to jest dziwne.

pytania

Jakie byłyby konsekwencje $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? Konsekwencja, o której już wiem, jest następująca: $\mathbf{PH}$ można by zredukować $\mathbf{NP}$ poprzez dwustronną randomizowaną redukcję. Innymi słowy, mielibyśmy $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ (używając twierdzenia Tody, które stwierdza, że $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$ , po prostu zastępując $\oplus\mathbf{P}$ z $\mathbf{NP}$ ). nie wiem czy $\mathbf{BPP}^{\mathbf{NP}}$ wykazano, że jest zawarty na pewnym poziomie $i$ Wielomianowej Hierarchii: jeśli tak, byłaby to kolejna konsekwencja $\mathbf{PH}$ zapada się do takiego poziomu $i$ . Ponadto zgodnie z powszechnie przyjętymi założeniami dotyczącymi derandomizacji ( $\mathbf{BPP} = \mathbf{P}$ ), tak jak my, hierarchia wielomianowa zawaliłaby się między pierwszym a drugim poziomem $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$ (Powiedziano mi, że to nieprawda, ale nie usunę tej linii, dopóki nie w pełni zrozumiem dlaczego).

Jeśli się nie mylę, wspomniana redukcja okazałaby się więcej niż $\oplus \mathbf{P} \subseteq \mathbf{NP}$ . To by się okazało $\oplus \mathbf{P} \subseteq \mathbf{UP}$ . Jakie byłyby konsekwencje $\oplus \mathbf{P} \subseteq \mathbf{UP}$ , oprócz tych już sugerowanych przez $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? Nie wiem dokładnie, czy $\oplus \mathbf{P} \subseteq \mathbf{UP}$ jeszcze bardziej zaskoczyłoby i tak już zaskakujące konsekwencje $\oplus \mathbf{P} \subseteq \mathbf{NP}$ , ani w jakim stopniu. Intuicyjnie zakładam, że tak, i to w dość szerokim zakresie.

— Giorgio Camerani
źródło

\oplus P

$\oplus\mathrm P$ jest zamknięty pod dopełnieniem, a losowa redukcja PH do

\oplus P

$\oplus\mathrm P$ stąd jest wiele-jeden

\oplus P \subseteq N P

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

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}$ , i

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}$ . UP nie robi dużej różnicy (por. Brak czegokolwiek przydatnego w cstheory.stackexchange.com/questions/3887 ).

— Emil Jeřábek

@ EmilJeřábek Dzięki za interesujący komentarz, nie wiedziałem o tych konsekwencjach. Znałem pytanie, które mi wskazałeś, jednak bym się tego spodziewał

\oplus P \subseteq U P

$\oplus \mathbf{P}\subseteq\mathbf{UP}$ (jak również

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$ ) być zaskakującym, przynajmniej dlatego, że

U P

$\mathbf{UP}$ nie wiadomo, że ma pełne problemy. Interesujące jest, jak coś powszechnie przypuszczano, że jest fałszywe (

N P \subseteq U P

$\mathbf{NP}\subseteq\mathbf{UP}$ ), nie ma, jeśli to prawda, żadnych szokujących konsekwencji. Możesz rozważyć rozszerzenie komentarza na odpowiedź ...

— Giorgio Camerani,

Nie, całkowicie się mylisz. BPP = P mówi tylko, że każdy język, który jest obliczalny przez maszynę BPP, jest również obliczalny przez maszynę P. Nie mówi nic o językach, które są obliczalne przez maszynę BPP z nietrywialną wyrocznią. Z twojego błędnego argumentu wynika, że NP = P

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

$\mathrm{NP}^A=\mathrm P^A$ dla każdego

A

$A$ , a zatem wiemy, że jest fałszywy

N P \neq P

$\mathrm{NP}\ne\mathrm P$ rozwiązano. A jeśli o to chodzi, twój argument sugerowałby

B P P \neq P

$\mathrm{BPP}\ne\mathrm P$ , ponieważ istnieją wyrocznie

A

$A$ dla którego

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

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

— Emil Jeřábek

@Giorgio: Twierdzi tylko, że rozważany przez ciebie tok rozumowania nie działa w takich okolicznościach. Odpowiednia część: „Jeśli maszyna, do której dołączam wyrocznię, jest co najmniej tak potężna, dlaczego nie powinno nastąpić włączenie?”. Nie wydaje się mówić, że samo twierdzenie jest fałszywe; tylko, że twoja konkretna intuicja nie działa. Nie możemy jeszcze wykluczyć, że probabilistyczne aspekty PPTM nie mogłyby więcej skorzystać z tej wyroczni. Probabilistyczna TM ma do dyspozycji więcej narzędzi, ale narzędzie może nie zapewnić wyraźnych korzyści bez dodatkowych (takich jak NP wyrocznia).

— mdxn

Nawet przy założeniu, że PRNG jest wystarczająco silny, aby zawalić P i BPP, nie rozumiem, dlaczego musi to oznaczać BPP z wyrocznią NP, a P z wyrocznią NP musi być taki sam. Zwykle PRNG mają gwarancję, że żaden obwód polaryzujący nie będzie w stanie odróżnić swojej mocy wyjściowej od naprawdę losowych bitów. Ale w przypadku maszyn wyroczni potrzebujesz gwarancji na każdy obwód polisizowy z dozwolonymi bramkami NP, a to jest silniejsze. Impagliazzo-Wigderson relatywizuje się, ale trzeba wzmocnić założenie dotyczące twardości ( eccc.hpi-web.de/report/1998/055/comment/1/download )

— Sasho Nikolov

Istnieją dwa zestawy wyroczni zdefiniowane w T88, takie jak ${\bf NP^A \not \subseteq \oplus P ^A}$ i ${\bf \oplus P^B \not \subseteq NP^B}$ .

— Tayfun Pay
źródło

czy jest jakaś konsekwencja w

P P \subseteq \oplus P

$PP\subseteq\oplus P$ trzyma?

— T ....