jako wyrocznia

Czy $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ trzymać?

Najwyraźniej $\mathsf{NP^{NP}\neq NP}$ , ale wydaje mi się, że $\mathsf{NP\cap coNP}$ jest „deterministyczna”, co pozwala mi wierzyć, że to prawda.

Czy istnieje prosty dowód (a może tylko z definicji)?

cc.complexity-theory complexity-classes oracles

— maomao
źródło

Po pierwsze tak. Rzeczywiście, oracle

spełnia

, wtedy i tylko wtedy, gdy

. Ta klasa nazywa się

lub czasami

: complexityzoo.uwaterloo.ca/Complexity_Zoo:L#lkp . Po drugie, nie sądzę, aby było zupełnie jasne, że

, chociaż jest to powszechnie przyjęte przekonanie. W szczególności oznacza to

A

$A$

{N P}^{A} = N P

$\mathsf{NP}^{A} = \mathsf{NP}$

A \in N P \cap c o N P

$A \in \mathsf{NP} \cap \mathsf{coNP}$

L o w (N P)

$\mathsf{Low(NP)}$

L_{1} P

$\mathsf{L_1 P}$

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

$\mathsf{NP}^{\mathsf{NP}} \neq \mathsf{NP}$

i wydaje się być silniejszy, ponieważ nie ma relatywnej implikacji w drugą stronę.

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$

— Joshua Grochow

Również ludzie, którzy uważają, że FACTORING jest trudny, mogą mieć problem z twoją intuicją, że

jest „deterministyczna”.

N P \cap c o N P

$\mathsf{NP \cap coNP}$

— Niel de Beaudrap

@JoshuaGrochow: Myślę, że powinieneś dodać to jako odpowiedź, z pewnym wyjaśnieniem, jakie są klasy w niskiej hierarchii; jest to tak dobra odpowiedź, jak prawdopodobnie uzyska OP.

— Niel de Beaudrap

zawiera

, więc być może to wyjaśnia, dlaczego jest to mało prawdopodobne, aby dorównać

N P^{N P}

$NP^{NP}$

c o - N P

$co-NP$

N P

$NP$

— domotorp

@NieldeBeaudrap: Moje wahanie przed opublikowaniem go jako odpowiedzi, a nie komentarza było takie, że chociaż uważam, że maomao naprawdę zadał to pytanie na poważnie, może być i było w przeszłości, jako zadanie domowe.

— Joshua Grochow

Tak. Rzeczywiście, oracle spełnia , wtedy i tylko wtedy, gdy . Ta klasa nazywa się lub czasami (patrz link i cytowany tam dokument, aby uzyskać ogólne wyjaśnienie niskiej hierarchii w ogóle). $A$ $\mathsf{NP}^A=\mathsf{NP}$ $A \in \mathsf{NP} \cap \mathsf{coNP}$ $\mathsf{Low(NP)}$ $\mathsf{L_1 P}$

Twoja intuicja dotycząca „determinizmu” jest w rzeczywistości nieco poprawna (chociaż nie jest wystarczająco deterministyczna, abyśmy mogli dojść do wniosku, że ). Spróbuj to jako ćwiczenie, a zobaczysz to intuicja zrehabilitowany: pierwszy koncert - ostrożnie, literowania szczegóły - że jeśli , a następnie . Dowiedzieć się dokładnie taką część swojego dowodu, że nie działa, jeśli tylko założyć, , a następnie zrozumieć, dlaczego ta część działa gdy $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$ $A \in \mathsf{P}$ $\mathsf{NP}^{A} = \mathsf{NP}$ $A \in \mathsf{NP}$ . $A \in \mathsf{NP} \cap \mathsf{coNP}$

(Pokazanie odwrotności też nie jest zbyt trudne: oznacza ) $\mathsf{NP}^A = \mathsf{NP}$ $A \in \mathsf{NP} \cap \mathsf{coNP}$

— Joshua Grochow
źródło