Apakah

Oleh http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf

Jika adalah bahasa PSPACE-lengkap, . $A$ $P^{A}=NP^{A}$

Jika adalah oracle waktu polinomial deterministik, (dengan asumsi ). $B$ $P^{B}\ne NP^{B}$ $P\ne NP$

adalah kelas masalah keputusan analog untuk dan , $PP$ $\#P$ $P\subseteq PP\subseteq PSPACE$

tetapi atau tidak diketahui. Tapi benarkah itu $P=PP$ $PP=PSAPCE$

? $coNP^{\#P}=NP^{\#P}=P^{\#P}$

cc.complexity-theory complexity-classes counting-complexity open-problem oracles Mike Chen
sumber

Jika

adalah waktu polinomial deterministik oracle, saya kira Anda berarti kita percaya

. (karena

dan

)

B

$B$

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

$P^B \neq NP^B$

P^{B} = P

$P^B = P$

N P^{B} = N P

$NP^B = NP$

Ramprasad

Saya mungkin salah, tetapi izinkan saya mencobanya: Pertanyaan pertama Anda mengasumsikan bahwa penyimpanan kedua tidak ketat. Dengan kata lain, diasumsikan bahwa PP = PSPACE. Dalam hal itu, saya pikir kesetaraan dipegang oleh hasil yang Anda sebutkan di awal. Apakah saya benar? (PS: Kebalikannya berlaku untuk pertanyaan ke-2.)

MS Dousti

Teorema Toda mungkin relevan di sini, karena menunjukkan seseorang mungkin dapat melipat perbedaan antara

dan

ke oracle

. (Tapi saya tidak 100% yakin tentang hal itu.)

P

$P$

N P

$NP$

#P

$#P$

Boaz Barak

Jawaban untuk pertanyaan keempat Anda adalah ya. Bahkan NP ^ PSPACE terkandung dalam PSPACE, jadi pasti NP dengan oracle #P ada di PSPACE.

Robin Kothari

Seperti komentar yang disarankan, beberapa pertanyaan yang dinyatakan dalam posting ini (dan beberapa pertanyaan yang baru Anda tambahkan) adalah dasar. Tolong tunjukkan beberapa bukti bahwa Anda benar-benar peduli. Lihat juga meta.cstheory.stackexchange.com/questions/300/… , meta.cstheory.stackexchange.com/questions/300/… .

Tsuyoshi Ito

Jawaban:

Ini adalah masalah terbuka dalam teori kompleksitas selama bertahun-tahun jika runtuh, di mana adalah hierarki waktu polinomial. Ini juga merupakan masalah terbuka untuk membangun sebuah oracle untuk memisahkan dari . $\mathsf{PH}^{\mathsf{\#P}}$ $\mathsf{PH}$ $\mathsf{P}^{\mathsf{\#P}}$ $\mathsf{PSPACE}$

Bin Fu
sumber

Selamat datang di CSTheory.SE, @Bin Fu! :)

Daniel Apon

Atau mungkin Anda pernah ke sini sebelumnya, tapi tetap saja selamat datang! ;)

Daniel Apon

Terima kasih, Daniel Apon. Diketahui bahwa PH ^ {Parity P} runtuh. Akan sangat menarik jika seseorang dapat membuktikan PH ^ {# P} runtuh.

Bin Fu

P H^{# P}

$PH^{\#P}$

Oleh http://portal.acm.org/citation.cfm?id=116858

$NP^{\mathbf{C}K}=\exists \mathbf{C}K$ $coNP^{\mathbf{C}K}=\forall\mathbf{C}K$

$K$ $\exists K\cup\forall K\subseteq\mathbf{C}K\subseteq\exists\mathbf{C}K\cap\forall\mathbf{C}K$

$K$ $P$ $PP\subseteq\exists PP\cap\forall PP$

$P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

$P^{\#P}=NP^{\#P}=coNP^{\#P}$

Mike Chen
sumber

Dimasukkannya P ^ X ⊆ NP ^ X ∩ coNP ^ X untuk setiap kelas X jelas dari definisi, dan Anda tidak memerlukan Teorema 4.1 dari Torán untuk ini. Saya tidak bisa melihat mengapa runtuhnya hierarki polinomial dan hierarki penghitungan menyiratkan P ^ # P = NP ^ # P = coNP ^ # P. Bisakah Anda menguraikan?

Tsuyoshi Ito

P = N P = c o N P

$P=NP=coNP$

P^{# P} = N P^{# P} = c o N P^{# P}

$P^{\#P}=NP^{\#P}=coNP^{\#P}$

C C P = C P

$\mathbf{C}\mathbf{C}P=\mathbf{C}P$

P P^{P P} = P P

$PP^{PP}=PP$

\exists K \cup \forall K \subseteq C K

$\exists K\cup\forall K\subseteq\mathbf{C}K$

P^{# P} \subseteq N P^{# P} \cap c o N P^{# P}

$P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

\subseteq N P^{# P} \cup c o N P^{# P} \subseteq P P^{P P}

$\subseteq NP^{\#P}\cup coNP^{\#P}\subseteq PP^{PP}$

= P P = P^{# P}

$=PP=P^{\#P}$

\subseteq

$\subseteq$

=

$=$

"Hirarki polinomial runtuh" tidak berarti P = NP, dan "hierarki penghitungan runtuh" tidak selalu berarti PP = PP ^ PP.

Tsuyoshi Ito

Selain itu, P = NP tidak menyiratkan P ^ # P = NP ^ # P sejauh yang saya tahu (tapi saya mungkin kehilangan sesuatu).

Tsuyoshi Ito

Kesalahan umum dalam jenis argumen ini adalah untuk menganggap relativizing ke oracle adalah operasi pada kumpulan bahasa, tetapi itu bukan operasi pada jenis perhitungan, yang secara drastis mempengaruhi bahasa apa yang ada di kelas.

Derrick Stolee