Contoh sesuatu yang berbeda untuk oracle generik dan acak?

Biarkan menjadi oracle generik dalam arti kategori Cohen / Baire. Biarkan menjadi oracle acak. $G$ $R$

Apakah ada kompleksitas kelas A dan B dengan atau sebaliknya,

A^{G} = B^{G} and A^{R} \neq B^{R}

$\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R$

A^{G} \neq B^{G} and A^{R} = B^{R} ?

$\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?}$

Pertanyaan itu diilhami oleh komentar oleh Scott Aaronson .

cc.complexity-theory complexity-classes Bjørn Kjos-Hanssen
sumber

Jawaban:

P = UP dengan generik (dengan asumsi P = PSPACE) tetapi mereka terpisah relatif terhadap oracle acak.

Di arah lain P = Janji-BPP relatif terhadap acak tetapi relatif terpisah untuk generik. Tidak bisa memikirkan kelas tanpa janji dari atas kepalaku.

Saya dapat melacak beberapa referensi jika Anda perlu.

Pembaruan: Jika Anda menginginkan versi yang tidak menjanjikan, dengan oracle acak (karena ) tetapi mereka terpisah dengan oracle generik (contoh dalam makalah saya dengan Yamakami ). $P^{NP} = S^p_2$ $S^p_2 \subseteq ZPP^{NP}$

Lance Fortnow
sumber

P = PSPACE sepertinya asumsi yang berani;)

Bjørn Kjos-Hanssen

Untuk mengklarifikasi komentar Bjorn: cara lain untuk mengungkapkannya adalah dengan pertama-tama relativize ke oracle PSPACE, kemudian membangun generik, dan kemudian Anda mendapatkan P = UP. Jadi ada oracle generik (relatif ke PSPACE-) yang membuat P = UP.

Joshua Grochow

Saya menambahkan contoh yang tidak dijanjikan. Anda juga perlu membuat beberapa asumsi karena jika P UP di dunia yang tidak terkait maka mereka tetap berbeda relatif terhadap generik. Atau Anda bisa menggunakan trik Josh.

\neq

$\neq$

Lance Fortnow

Saya tidak berpikir kita tahu perbedaan seragam tanpa syarat / kompleksitas kelas non-janji dalam bentuk di atas (pembaruan: lihat jawaban Lance Fortnow untuk contoh), tetapi perbandingan berikut dari nubuat generik dengan nubuat acak mungkin membantu.

Sebuah oracle generik adalah dengan membangun sebuah oracle yang memenuhi setiap properti yang tidak dapat dikesampingkan dengan memperbaiki segmen awal yang terbatas. Dalam arti tertentu, segala sesuatu yang mungkin terjadi mungkin terjadi, yang membuatnya sangat berbeda dari oracle acak (meskipun ia juga sering mengemulasi oracle acak). $Σ^0_1$

Misalnya, dengan oracle generik (io berarti tak terhingga sering)
PSPACE ⊆ io-P
EXP ⊆ io-ZPP
EXP ^NP ⊆ io-BPP

Jadi, untuk setiap masalah dalam PSPACE yang direlatifikasi, ada algoritme waktu polinomial (menggunakan oracle) yang untuk tak terhingga banyaknya ukuran input memecahkan semua contoh ukuran itu (dan juga dengan ZPP dan BPP dengan perilaku sewenang-wenang pada ukuran input yang 'buruk') .

Seperti oracle acak:
IP <PSPACE
Hirarki polinomial tidak terbatas.

Setiap fungsi rekursif dihitung dalam waktu polinomial dengan oracle generik dapat dihitung dalam waktu polinomial tanpa oracle (karena oracle kosong untuk peregangan cukup lama). Jadi, jika P <BPP, maka ini juga berlaku untuk oracle generik, sedangkan untuk oracle acak P = BPP.

Dmytro Taranovsky
sumber

Apa yang Anda maksud dengan = io antara kelas-kelas bahasa?

Kaveh

Jadi, dengan "P = ioPSPACE" yang Anda maksud adalah PSPACE ioP? Cukup membingungkan. Mengapa Anda memindahkan awalan io ke kelas lain?

\subseteq

$\subseteq$

Emil Jeřábek

@ Kaveh A = io B berarti ada himpunan S yang tak terbatas sehingga A ⊆ SB dan B ⊆ SA (di mana SB didefinisikan secara analog dengan io-B). Namun, karena penggunaan ini tidak standar, saya mengubah jawaban saya untuk menggunakan ⊆ io

Dmytro Taranovsky

@ EmilJeřábek Saya mengganti = io dengan standar ⊆ io

Dmytro Taranovsky

Saya tahu apa artinya untuk bahasa, saya bertanya apa artinya untuk kelas bahasa. io-C masuk akal untuk kelas C, = io sebagai relasi sepertinya tidak masuk akal seperti yang Anda tulis semula.

Kaveh