Apakah ada oracle sehingga ?

Latar Belakang

Kita tahu bahwa . $P^{\#P} \subseteq PSPACE$

Selain itu, kami tahu dari teorema Toda bahwa . $PH \subseteq P^{\#P}$

Untuk latar belakang lebih lanjut tentang , lihat di sini: https://en.wikipedia.org/wiki/Sharp-P $\#P$

Pertanyaan

Apakah ada oracle sehingga ? $A$ $(P^{\#P})^{A} \neq PSPACE^{A}$

cc.complexity-theory complexity-classes oracles relativization pspace Michael Wehar
sumber

Saya akan menebak bahwa untuk bagian pertama, pengaturan

sudah cukup, bukan? Benarkah

A = PSPACE

$A=\textrm{PSPACE}$

{PSPACE}^{PSPACE} = PSPACE

$\textrm{PSPACE}^{\textrm{PSPACE}} = \textrm{PSPACE}$

Michael Lampis

@MichaelLampis Yap, jika Anda menghitung spasi pada rekaman kueri, maka itu terdengar tepat untuk saya! :)

Michael Wehar

Bagus, terima kasih banyak sudah menunjukkannya! Saya memodifikasi pertanyaan dengan menghilangkan bagian yang lebih mudah tentang menemukan oracle di mana mereka setara. :)

Michael Wehar

Ada oracle yang memisahkan PP dari PSPACE: Jacobo Toran, Sebuah teknik kombinatorial untuk memisahkan penghitungan kelas kompleksitas, ICALP 1989. Hasil terbaik untuk P ^ PP yang saya tahu adalah hasil kondisional oleh Heribert Vollmer: Menghubungkan waktu polinomial ke kedalaman konstan. TCS, 207: 159-170, 1998.

Markus Bläser

@ MarkusBläser Saya pikir Anda harus memposting ini sebagai jawaban.

Emil Jeřábek

Jawaban:

Atas permintaan populer, inilah komentar saya sebagai jawaban:

Ada oracle yang memisahkan dari : Jacobo Toran, Sebuah teknik kombinatorial untuk memisahkan kelas kompleksitas penghitungan, ICALP 1989. Hasil terbaik untuk yang saya tahu adalah hasil kondisional oleh Heribert Vollmer: Mengaitkan polinomial waktu ke kedalaman konstan. TCS, 207: 159-170, 1998. $\mathrm{PP}$ $\mathrm{PSPACE}$ $\mathrm{P}^\mathrm{PP}$

Markus Bläser
sumber

Hanya untuk memastikan kita berada di halaman yang sama, apakah diketahui bahwa

P^{P P} = P^{# P}

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

Michael Wehar

Tampaknya lurus ke depan bahwa

, tetapi arah yang lain agak rumit. Anda melakukan semacam pencarian biner untuk menghitung jumlah solusi untuk pemverifikasi?

P^{P P} \subseteq P^{# P}

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

Michael Wehar

Yap, kompleksitas kebun binatang mengatakan bahwa mereka setara. Juga, saya pikir saya ingat membuktikan ini dalam kursus teori kompleksitas beberapa tahun yang lalu sebagai latihan. :)

Michael Wehar

Kompleksitas kebun binatang juga mengatakan bahwa pertanyaan utama saya adalah masalah terbuka. Maaf, saya tidak menyadarinya. Saya pikir mungkin seseorang di luar sana telah menyelesaikannya.

Michael Wehar