Kelas kompleksitas yang berpotensi setara tanpa relativiasi kontradiktif yang diketahui

Apa saja contoh pasangan kompleksitas kelas dan sedemikian rupa sehingga $A$ $B$

kita tidak tahu apakah , dan $A=B$
kita tidak tahu relativiasi kontradiktif juga (yaitu, kita tidak tahu orakel dan sehingga dan )? $P$ $Q$ $A^P = B^P$ $A^Q \ne B^Q$

Untuk ungkapan pertanyaan dengan cara lain, apa saja pengecualian untuk heuristik bahwa jika tidak dapat menemukan relativiasi yang kontradiktif maka mudah untuk menyelesaikan pertanyaan kesetaraan langsung?

cc.complexity-theory complexity-classes relativization Timothy Chow
sumber

Apakah ada dua kelas A dan B yang kita tidak tahu bagaimana membuktikan pemisahan oracle antara A dan B sudah cukup untuk menjawab pertanyaan Anda? (Dengan asumsi dimungkinkan untuk A dan B menjadi sama.)

Robin Kothari

Apakah Anda akan menerima contoh tentang implikasi antara persamaan, bukan persamaan tunggal? Misalnya, kami tidak tahu apakah NP = UP menyiratkan bahwa PH runtuh, tetapi kami juga tidak memiliki oracle di mana implikasi ini salah.

Joshua Grochow

@ JoshuaGrochow: Itu menarik, meskipun saya sedikit lebih tertarik pada jenis contoh spesifik yang saya jelaskan.

Timothy Chow

@Robin Kothari: Jika kita tidak tahu oracle Q, maka fortiori kita tidak tahu oracle P dan Q, jadi satu-satunya cara saya melihat (A, B) untuk memenuhi kebutuhan Anda tetapi bukan milik saya adalah jika kita tahu bahwa A = B tetapi kita tidak tahu oracle yang memisahkan mereka. Saya kira mungkin menarik untuk melihat contoh A dan B sehingga A = B namun masuk akal (tetapi tidak diketahui) bahwa mereka dapat dipisahkan oleh oracle, tetapi ini sebenarnya bukan yang saya minta.

Timothy Chow

Jawaban:

Saya pikir contoh terbesar saat ini adalah (waktu polbomial kuantum) vs (hierarki waktu polinomial). $BQP$ $PH$ Upaya signifikan telah dilakukan untuk memisahkan mereka relatif terhadap nubuat, tanpa hasil. (Tentu saja oracle cukup kuat akan membuat mereka sama.) Dan hasil terbaik penahanan diketahui adalah bahwa adalah . $BQP$ $PP$

Beberapa referensi untuk serangan pada masalah oracle: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

Ryan Williams
sumber

Sebenarnya hasil terbaik dikenal adalah

, di mana

adalah (antara lain) yang sublcass kesenjangan-didefinisikan terbesar

sehingga

. Saya tidak mengetahui adanya kepentingan di kelas

terpisah dari hubungannya dengan

, sehingga sebuah perbaikan ini adalah sedikit dari segi teknis, tapi ada Anda pergi.

B Q P \subseteq A W P P \subseteq P P

$\mathsf{BQP \subseteq AWPP \subseteq PP}$

A W P P

$\mathsf{AWPP}$

P P

$\mathsf{PP}$

P P^{A W P P} = P P

$\mathsf{PP^{AWPP} = PP}$

A W P P

$\mathsf{AWPP}$

B Q P

$\mathsf{BQP}$ dan

P P

$\mathsf{PP}$

Niel de Beaudrap

Sejalan dengan ini, juga tidak diketahui bagaimana memisahkan BQP dari AM, atau bahkan QMA dari AM.

Robin Kothari

Apakah ada oracle yang diketahui memisahkan dari ? $\mathsf{P}^{\#\mathsf{P}}$ $\mathsf{PSPACE}$

Ryan O'Donnell
sumber

Saya cukup yakin pertanyaan itu dimaksudkan lebih retoris, yaitu "Saya pikir ini adalah jawaban, tapi mungkin ada oracle yang saya tahu tidak tahu"

Joshua Grochow

Ya terima kasih Josh. Apakah kamu kenal satu? Sangat sulit untuk mencari, tetapi saya ingat tidak dapat mengetahui keberadaan seseorang terakhir kali saya mencoba.

Ryan O'Donnell