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.

cc.complexity-theory graph-theory complexity-classes sat counting-complexity 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

Konsekwencje

Odpowiedzi: