Hasil Oracle pada P vs BPP

10

Biarkan menjadi masalah lengkap EXP. Kemudian, . $A$ $P^A = NP^A$

Mari ada beberapa oracle yang memperhitungkan rekening permintaan yang (TM di P) akan membuat, dan kita bisa mendapatkan . $B$ $M$ $P^B \neq NP^B$

Pertanyaan: Apakah kami memiliki hasil oracle yang serupa untuk P vs BPP?

cc.complexity-theory oracles relativization Kaveh
sumber

2

Ya kita lakukan, tetapi saya tidak yakin saya dapat menemukan kutipan. (Nah, bagian pertama mudah, berikan kedua kelas oracle untuk masalah lengkap EXP.)

Robin Kothari

3

Jika Anda menganggap pengaturan PCP sebagai verifier yang memiliki akses oracle ke prover (di mana query oracle akan mengembalikan bit buktinya) maka kami tahu bahwa jika Anda mengizinkan verifier menjadi mesin BPP dengan randomness dan pertanyaan kemudian kelas bahasa dihitung adalah dan ketika verifier adalah mesin P (yang ada keacakan) dengan (bahkan dengan ) query kemudian kelas bahasa dihitung adalah . Ini tidak menunjukkan pemisahan oracle kecuali . Tetapi hanya sebuah contoh di mana akses oracle ke "tampaknya" lebih kuat.

i

$i$

i^{t h}

$i^{th}$

\log n

$\log n$

3

$3$

N P

$NP$

3

$3$

\log n

$\log n$

P

$\bf P$

P \neq N P

$\bf P \neq \bf NP$

B P P

$\bf BPP$

Sajin Koroth

@RobinKothari Mari maka jika adalah masalah lengkap, kita tidak memiliki (ketimpangan terakhir berdasarkan hierarki waktu)? Lalu apakah sementara ditampilkan?

\oplus P = N P = E X P

$\oplus P=NP=EXP$

A

$A$

E X P

$EXP$

N P^{A} = N P^{\oplus P} = \oplus P^{\oplus P} = \oplus P = N P = E X P \neq P

$NP^A=NP^{\oplus P}=\oplus P^{\oplus P}=\oplus P=NP=EXP\neq P$

P^{A} = N P^{A} ⟹ P^{\oplus P} = N P = \oplus P

$P^A=NP^A\implies P^{\oplus P}=NP=\oplus P$

P \neq N P

$P\neq NP$

T ....

13

Saya memiliki ingatan yang samar-samar bahwa saya tahu referensi yang bagus untuk pemisahan oracle semacam itu. Saya akhirnya menemukannya.

Referensi hebat untuk pemisahan oracle (untuk kelas antara P dan PSPACE) adalah makalah berikut :

Vereshchagin, NK (1994), "TEOREM YANG DAPAT DIANDALKAN DAN TIDAK DAPAT DIPERLUASKAN DALAM TEORI ALGORITMA POLINOMIAL", Akademi Ilmu Pengetahuan Rusia. Izvestiya Matematika 42 (2): 261

Makalah ini menunjukkan (atau memberikan kutipan untuk) pemisahan oracle antara hampir setiap pasangan kelas yang mungkin Anda pedulikan antara P dan PSPACE (misalnya, memiliki kelas seperti P, RP, BPP, UP, FewP, NP, MA, AM , level lain dari PH, PH, IP, PSPACE, dll.).

Misalnya, Teorema 8 menunjukkan masalah oracle di coRP yang tidak ada di NP. Karena (relatif terhadap semua nubuatan) coRP berada di BPP dan NP mengandung P, kami mendapatkan masalah oracle di BPP yang tidak dalam P.

Seperti yang saya sebutkan di komentar saya, menunjukkan oracle yang mudah. Biarkan A menjadi bahasa lengkap-EXP atau bahasa lengkap-PSPACE. $\text{P}^A = \text{BPP}^A$

Robin Kothari
sumber

di sini adalah tautan unduhan gratis dari citeseer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1232

Marcos Villagra

Meskipun jika Anda bisa mendapatkan versi lengkap, saya akan merekomendasikan itu sebagai gantinya. Versi citeseer tidak memiliki angka dan karena itu kehilangan diagram kelas inklusi kompleksitas yang bagus (Gbr 1).

Robin Kothari

8

The Kompleksitas kebun binatang adalah teman Anda! Seperti yang dikatakan Robin, Anda memiliki separuh jawaban: setiap masalah EXP-complete meruntuhkan NP ke P, dan karena itu BPP ke P. Buhrman dan Fortnow membuat oracle relatif yang P = RP tetapi BPP tidak sama dengan P. Ini lebih dari apa yang Anda minta; Saya menduga ada konstruksi yang lebih mudah yang memisahkan P dari RP dan BPP.

Sasho Nikolov
sumber

6

Deskripsi yang bagus tentang oracle yang memisahkan P dan BPP diberikan oleh Greg Kuperberg dalam salah satu komentar dari posting blog yang menarik ini , di mana Terence Tao menggambarkan mesin Turing dengan nubuat dan hasil kerumitan relatif terhadap nubuat dalam bentuk alegori.

Alessandro Cosentino
sumber

1

itu deskripsi yang keren :)

Sasho Nikolov

-1

Bennett & Gill memberikan orakel untuk kedua kasus: http://epubs.siam.org/doi/abs/10.1137/0210008

Luke Mathieson
sumber

Apakah mereka memberi oracle untuk memisahkan BPP dari P? Saya tidak dapat menemukan klaim seperti itu di koran.

Robin Kothari

Saya pikir begitu, sayangnya saya jauh dari kantor saya jadi tidak punya akses ke pdf. Saya harus memeriksanya nanti.

Luke Mathieson

B P P^{A} = P^{A}

$BPP^{A} = P^{A}$

Hasil Oracle pada P vs BPP

Jawaban: