Robi

10

Czy z dostępem Oracle do większy niż ? Rozumiem, że to tylko maszyna Turinga, która może wysyłać zapytania do innej maszyny , jeśli tak, to może symulować ? Czy coś jest nie tak z tym argumentem? $NP$ $NP$ $NP$ $NP^ {NP}$ $NP$ $NP$ $NP^{NP}$

complexity-theory

16

Odpowiedź brzmi : nie wiemy , a fakt, że jeszcze nie wiemy, jest dość dobrze ustalonym statusem tego problemu. Klasa jest również znana jako i jest klasą na drugim poziomie hierarchii wielomianowej . Prostym powodem, dla którego nie możemy po prostu symulować wyroczni NP za pomocą maszyny NP , jest to, że nie wiemy, w jaki sposób maszyna NP może wykryć przypadki „braku”.

{N P}^{N P}

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

Σ_{2}^{P}

$\Sigma^{P}_2$

Dlaczego taki sam jak ?

N P^{N P}

$NP^{NP}$

Σ_{2}^{P}

$\Sigma_2^P$

5

To jest po prostu jak jest zdefiniowana. Przeczytaj stronę Wikipedii lub podręcznik dotyczący złożoności obliczeniowej, który obejmuje hierarchię wielomianową.

Σ_{2}^{P}

$\Sigma_2^P$

13

Aby sformułować moje komentarze jako odpowiedź i nieco rozwinąć:

Nie wiemy, czy NP ^NP = NP - jest to powszechnie otwarty problem w teorii złożoności, chociaż jak w przypadku P w porównaniu z NP podejrzewamy, że nie są one równe. Jednym z powodów, dla których nie wiemy, jak symulować wyrocznię NP za pomocą maszyny NP , jest to, że nie wiemy, w jaki sposób maszyna NP może wykryć „brak” przypadków problemów przesłanych do wyroczni.

Klasa NP ^NP jest również znana jako i jest jedną z klas na drugim poziomie hierarchii wielomianowej . Pozostałe klasy na drugim poziomie to (Wszystkie te klasy byłyby takie same, gdybyśmy użyli wyroczni coNP ; jedyną różnicą jest w istocie logiczna negacja wyniku). Klasy trzeciego i wyższego poziomu hierarchii są zdefiniowane przez podanie jeszcze inne wyrocznie NP : $\Sigma_2^P$

\begin{aligned} Δ_{2}^{P} & := P^{N P}, \\ Π_{2}^{P} & := {c o N P}^{N P} . \end{aligned}

$\begin{align*} \Delta_2^P &:= \mathsf{P}^{\mathsf{NP}}, \\ \Pi_2^P &:= \mathsf{coNP}^{\mathsf{NP}}. \end{align*}$

\begin{aligned} Δ_{k + 1}^{P} & := P^{Σ_{k}^{P}} = P^{Π_{k}^{P}}, \\ Σ_{k + 1}^{P} & := {N P}^{Σ_{k}^{P}} = {N P}^{Π_{k}^{P}}, \\ Π_{k + 1}^{P} & := {c o N P}^{Σ_{k}^{P}} = {c o N P}^{Π_{k}^{P}} . \end{aligned}

$\begin{align*} \Delta_{k+1}^P &:= \mathsf{P}^{\,\Sigma_{k}^P} = \mathsf{P}^{\,\Pi_k^P}, \\[1ex] \Sigma_{k+1}^P &:= \mathsf{NP}^{\,\Sigma_{k}^P} = \mathsf{NP}^{\,\Pi_k^P}, \\[1ex] \Pi_{k+1}^P &:= \mathsf{coNP}^{\,\Sigma_{k}^P} = \mathsf{coNP}^{\,\Pi_k^P}. \\\end{align*}$ Again, the difference between the

Σ_{k}^{P}

$\Sigma_k^P$ and

Π_{k}^{P}

$\Pi_k^P$ oracles is essentially negation of its output. We also define

Δ_{0}^{P} = Σ_{0}^{P} = Π_{0}^{P} = P

$\Delta_0^P = \Sigma_0^P = \Pi_0^P = \mathsf{P}$ ; using the definition above, you can see that this gives us

Δ_{1}^{P} := P

$\Delta_1^P := \mathsf{P}$ ,

Σ_{1}^{P} := N P

$\Sigma_1^P := \mathsf{NP}$ , and

Π_{1}^{P} := c o N P

$\Pi_1^P := \mathsf{coNP}$ .

The various classes of the polynomial hierarchy are thought to be distinct; that is, no matter how many layers of NP oracles you provide, the computational power is not thought to stabilize at any point. If NP^NP = NP, then the polynomial hierarchy collapses to it's first level: all of the $\Sigma_k^P$ classes for k ≥ 1 would be equal to NP (as would, for that matter, all of the $\Pi_k^P$ classes including coNP, as an NP machine could solve any problem in $\Pi_k^P$ by simulating some tower of NP oracles).

— Niel de Beaudrap
źródło

5

$\mathsf{NP}^{\mathsf{NP}}$ is known as the second level of polynomial hierarchy.

It is suspected that all levels of polynomial hierarchy are different. A machine with NP oracle can query it and negate the answer, therefore $\mathsf{NP}^{\mathsf{NP}} \supseteq \mathsf{coNP}$ , while $\mathsf{NP} \supseteq \mathsf{coNP}$ seems unlikely.

— sdcvvc
źródło