Apakah ?

10

Apakah dengan akses oracle ke lebih besar dari sekedar ? Seperti yang saya pahami hanyalah mesin turing yang dapat membuat permintaan ke mesin lain jika demikian daripada dapat mensimulasikan ? Apakah ada yang salah dengan argumen ini? $NP$ $NP$ $NP$ $NP^ {NP}$ $NP$ $NP$ $NP^{NP}$

complexity-theory
sumber

16

Jawabannya adalah kita tidak tahu , dan fakta bahwa kita belum tahu adalah status yang cukup mapan untuk masalah ini. Kelas

{N P}^{N P}

$\mathsf{NP}^{\mathsf{NP}}$ juga dikenal sebagai

Σ_{2}^{P}

$\Sigma^{P}_2$ , dan merupakan kelas di tingkat kedua dari hierarki polinomial . Alasan sederhana mengapa kita tidak bisa hanya mensimulasikan oracle NP dengan mesin NP adalah bahwa kita tidak tahu bagaimana mesin NP bisa mendeteksi contoh "tidak".

Mengapa

N P^{N P}

$NP^{NP}$ sama dengan

Σ_{2}^{P}

$\Sigma_2^P$ ?

5

Yang hanya bagaimana didefinisikan. Silakan baca halaman Wikipedia, atau buku teks tentang kompleksitas komputasi yang mencakup hierarki polinomial.

Σ_{2}^{P}

$\Sigma_2^P$

13

Untuk merumuskan kembali komentar saya sebagai jawaban, dan sedikit memperluas:

Kami tidak tahu apakah NP ^NP = NP - ini adalah masalah yang sangat terbuka dalam teori kompleksitas, meskipun seperti dengan P versus NP kami menduga bahwa mereka tidak sama. Salah satu alasan mengapa kita tidak tahu bagaimana mensimulasikan oracle NP dengan mesin NP adalah bahwa kita tidak tahu bagaimana mesin NP bisa mendeteksi "tidak" contoh masalah yang diajukan ke oracle.

Kelas NP ^NP juga dikenal sebagai , dan merupakan salah satu kelas di tingkat kedua dari hirarki polinomial . Kelas-kelas lain di tingkat kedua adalah (Semua kelas ini akan sama jika kita menggunakan oracle coNP ; satu-satunya perbedaan pada dasarnya adalah negasi logis dari output.) Kelas-kelas dari level hirarki ketiga dan lebih tinggi didefinisikan dengan memberikan mereka lebih lanjut nubuat 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*}$ Sekali lagi, perbedaan antara dan pada dasarnya adalah negasi dari outputnya. Kami juga mendefinisikan ; menggunakan definisi di atas, Anda dapat melihat bahwa ini memberi kami , , dan .

Σ_{k}^{P}

$\Sigma_k^P$

Π_{k}^{P}

$\Pi_k^P$

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

$\Delta_0^P = \Sigma_0^P = \Pi_0^P = \mathsf{P}$

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

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

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

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

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

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

Berbagai kelas hierarki polinom dianggap berbeda; yaitu, tidak peduli berapa banyak lapisan oracle NP yang Anda berikan, kekuatan komputasi tidak dianggap stabil pada titik mana pun. Jika NP ^NP = NP , maka hierarki polinomial runtuh ke level pertama : semua kelas untuk k ≥ 1 akan sama dengan NP (seperti halnya, dalam hal ini, semua kelas termasuk coNP , sebagai mesin NP dapat memecahkan masalah dalam dengan mensimulasikan beberapa menara NP oracle). $\Sigma_k^P$ $\Pi_k^P$ $\Pi_k^P$

Niel de Beaudrap
sumber

5

$\mathsf{NP}^{\mathsf{NP}}$ dikenal sebagai level kedua dari hierarki polinomial .

Diduga bahwa semua tingkat hierarki polinomial berbeda. Mesin dengan NP oracle dapat menanyakannya dan meniadakan jawabannya, oleh karena itu , sedangkan tampaknya tidak mungkin . $\mathsf{NP}^{\mathsf{NP}} \supseteq \mathsf{coNP}$ $\mathsf{NP} \supseteq \mathsf{coNP}$

sdcvvc
sumber

Apakah ?

Jawaban: