Wyrocznia do oddzielenia NP od CoNP

12

Jak udowodnić, że ? Właśnie szukam takiej wyroczni TM i języka rekurencyjnego dla którego to się utrzymuje. $\mathsf{NP}^A \neq \mathsf{coNP}^A$ $M$ $L(M) = L$

Znam dowód gdzie można pokazać, że nie jest wyrocznią takie, że i wyrocznią takie, że . Mam wskazówkę, że powinienem znaleźć taką wyrocznię , rozszerzając dowód ale gdziekolwiek szukam i czytam, wszędzie jest „oczywiste” lub „proste”, ale po prostu nie rozumiem, jak to udowodnić. . $A$ $\mathsf{P}^A \neq \mathsf{NP}^A$ $A$ $\mathsf{P}^A = \mathsf{NP}^A$ $A$ $\mathsf{P}^A \neq \mathsf{NP}^A$

complexity-theory relativization

— Stewenson
źródło

6

Nie jest jasne, czy podążałeś za wskazówkami. Jestem zaskoczony, że

jest oczywista, ale można znaleźć dowód w (na przykład) Computational Złożoność: A Modern Approach przez Arora i Barak.

P^{A} \neq N P^{A}

$P^A \neq NP^A$

9

$\mathsf{coNP}$

Wyjaśnię wymaganą modyfikację poniżej, ale najpierw spójrzmy na oryginalny dowód.

$A=\bigcup_n A_n$ $i$ $i$ $\mathsf{P}$ $M_i$ $\{x \mid \exists y\in A \ |x|=|y| \}$ $\mathsf{NP}^A$

$M_i$ $A$ $0^m$ $m$ $M_i$ $m$ $M_i$ $m$ $M_i$ $A$ $m$ lub mniej pozostanie taki sam). Daje to pewność, że nie zdecyduje poprawnie w języku i dokończy dowód. $M_i^A$

Następnie, zakłada się, że maszyny były w miejscu . Musimy zmodyfikować dowód, aby upewnić się, że nie rozpozna . Jeśli się zgadza, zachowujemy jak poprzednio i wszystko działa dobrze, jak w oryginalnym dowodzie. Jeśli odrzuci, musimy dodać ciąg do zestawu, aby upewnić się, że nie odpowiada poprawnie. Nadal możemy symulować za pomocą części którą mamy, problem polega na tym, że może sprawdzać wszystkie ciągi długości . W tym przypadku sposób, w jaki $M_i$ $\mathsf{coNP}$ $\mathsf{P}$ $M_i^A$ $L$ $A$ $M_i$ $A$ $M_i$ $n$ $\mathsf{coNP}$ $m$ $A$

$A$ $\mathsf{DSpace}(n^{\omega(1)})$

— Kaveh
źródło

3

$P^A = NP^A$ $P^B \not= NP^B$ $A$ $B$

— Vincent Russo
źródło