Apakah diketahui apakah

10

Inklusi terbalik jelas, karena fakta bahwa setiap bahasa NP yang dapat direduksi sendiri dalam BPP juga dalam RP. Apakah ini juga diketahui berlaku untuk bahasa NP yang tidak dapat direduksi sendiri?

bppcapnpvsrp
sumber
2
Jika diketahui, dari inklusi R PB P PRPBPP dan R PN PRPNP , maka akan mengikuti bahwa B P P = R PBPP=RP atau R P = N PRP=NP (atau keduanya, pada dasarnya tergantung pada hubungan antara B P PBPP dan N P.NP Jadi saya pikir aman untuk mengasumsikan bahwa saat ini tidak diketahui. Karena R PRP memiliki kesalahan satu sisi, mudah untuk melihat bagaimana itu terkandung dalam B P PBPP, tanpa perlu direduksi sendiri atau properti lainnya.
chazisop
4
Apa yang diketahui adalah bahwa N PB P PN P B P P menyiratkan NP = RP. @ chisop, dari mana Anda dapatkan bahwa N PB P P = R PN P B P P = R P menyiratkan BPP = RP atau NP = RP?
Emil Jeřábek
1
Misalkan kita tahu B P P N P R P ( 1 )BPPNPRP(1) . Maka kita bisa melakukan analisis kasus: - Jika B P P N PBPPNP , maka dari (1) N P R PNPRP , yang dengan hasil dikenal menyiratkan N P = R PNP=RP . - Jika N P B P PNPBPP , maka dari (1) B P P R PBPPRP , yang dengan hasil yang diketahui menyiratkan B P P= R PBPP=RP . - Jika N P B P PNPBPP (tidak ada bagian dari yang lain), maka kita mendapatkan. PS: Maaf karena menghapus komentar sebelumnya, saya tidak sengaja mempostingnya di tengah komentar dan tidak dapat mengeditnya untuk memasukkan sisa kasus. B P P N P = R PBPPNP=RP
chazisop
4
Anda punya dua kasus pertama dicampuradukkan. Lebih penting lagi, dalam kasus ketiga, generik, kesimpulan Anda identik dengan asumsi, sehingga seluruh argumen tidak mencapai apa pun. Secara khusus, itu tidak mendukung klaim yang salah dalam komentar pertama Anda.
Emil Jeřábek
1
Asumsinya hanya meminta subset, bukan persamaan. Bagaimanapun, argumen saya (bahkan diformat dengan buruk dan dengan kesalahan), memang menunjukkan bahwa jika kita tahu apa yang ditanyakan, maka kita dapat memperoleh kompleksitas hubungan kelas yang saat ini menjadi masalah terbuka. Selanjutnya, saya gagal melihat bagaimana kasus ketiga jika lebih umum daripada yang lain: secara eksplisit mengecualikan kemungkinan satu kelas berisi yang lain, yang saat ini tidak diketahui.
chazisop

Jawaban:

7

Seperti kebanyakan pertanyaan dalam kompleksitas, saya tidak yakin akan ada jawaban lengkap untuk waktu yang sangat lama. Tetapi setidaknya kita dapat menunjukkan bahwa jawabannya adalah non-relativizing: ada nubuat relatif yang memegang ketidaksetaraan dan satu relatif yang dimiliki kesetaraan. Ini cukup mudah untuk memberikan oracle relatif yang kelasnya sama: setiap oracle yang memiliki B P P = R P akan bekerja (misalnya setiap oracle relatif yang "keacakan tidak banyak membantu"), seperti halnya oracle yang memiliki N PB P P (misalnya oracle relatif yang "keacakan banyak membantu"). Ada banyak ini, jadi saya tidak akan repot dengan spesifik.B P P = R PN P B P P

Ini agak lebih menantang, meskipun masih cukup mudah, untuk merancang sebuah oracle relatif terhadap mana kita mendapatkan R PB P PN P . Konstruksi di bawah ini sebenarnya sedikit lebih baik: untuk konstanta c , ada oracle relatif yang ada bahasa di c o R PU P yang tidak dalam R P T I M E [ 2 n c ] . Saya akan uraikan di bawah ini.R P B P P N Pcc o R P U PR P T I M E [ 2nc]

Kami akan merancang oracle A yang berisi string dari bentuk ( x , b , z ) , di mana x adalah string n- bit, b adalah bit tunggal, dan z adalah string bit dengan panjang 2 n c . Kami juga akan memberikan bahasa L A yang akan diputuskan oleh mesin c o R P dan mesin U P sebagai berikut:SEBUAH(x,b,z)xnbz2ncLAcoRPUP

  • Mesin c o R P , pada input x , menebak z dengan panjang 2 | x | c secara acak, kueri ( x , 0 , z ) , dan menyalin jawabannya.coRPxz2|x|c(x,0,z)
  • The U P mesin, masukan x , tebakan z panjang 2 | x | c , kueri ( x , 1 , z ) , dan menyalin jawabannya.UPxz2|x|c(x,1,z)

Untuk membuat mesin yang ditentukan di atas benar-benar memenuhi janjinya, kita perlu A untuk memenuhi beberapa properti. Untuk setiap x , salah satu dari dua opsi ini harus menjadi kasus:Ax

  • Opsi 1: Pada kebanyakan setengah dari z pilihan memiliki ( x , 0 , z ) A dan nol z pilihan memiliki ( x , 1 , z ) A . (Dalam hal ini, x L A. )z(x,0,z)A z(x,1,z)AxLA
  • Opsi 2: Setiap z pilihan memiliki ( x , 0 , z ) A dan tepat satu z pilihan memiliki ( x , 1 , z ) A . (Dalam hal ini, x L A. )z(x,0,z)A z(x,1,z)AxLA

Tujuan kami adalah untuk menentukan A memuaskan janji-janji ini sehingga L A mendiagonalisasi terhadap setiap R P T I M E [ 2 n c ] mesin. Untuk mencoba membuat jawaban yang sudah lama ini singkat, saya akan menjatuhkan mesin konstruksi oracle dan banyak detail yang tidak penting, dan menjelaskan cara mendiagonalisasi terhadap mesin tertentu. Perbaiki M sebagai mesin Turing acak, dan biarkan x menjadi input sehingga kita memiliki kontrol penuh atas pemilihan b dan z sehingga ( x , b , zALARPTIME[2nc]Mxbz) A . Kami akan memecah M pada x .(x,b,z)AMx

  • Kasus 1: Misalkan ada cara untuk memilih z sehingga A memenuhi opsi pertama dari janjinya, dan M memiliki pilihan keacakan yang menerimanya. Maka kita akan komit A untuk seleksi ini. Kemudian M tidak dapat secara bersamaan memenuhi R P janji dan menolak x . Namun demikian, x L A . Jadi kita telah didiagonalkan terhadap M .zAMAMRPxxLAM

  • Kasus 2: Selanjutnya, asumsikan bahwa kasus sebelumnya tidak berhasil. Sekarang kita akan menunjukkan bahwa kemudian M dapat dipaksa baik untuk memecahkan R P janji atau menolak pada beberapa pilihan A memuaskan pilihan kedua dari janjinya. Ini mendiagonalisasi terhadap M . Kami akan melakukan ini dalam dua langkah:MRPAM

    1. Tunjukkan bahwa untuk setiap pilihan tetap r dari M bit acak 's, M harus menolak ketika semua pertanyaan yang dalam bentuk ( x , 0 , z ) berada di A dan semua pertanyaan yang dalam bentuk ( x , 1 , z ) tidak dalam A .rMM(x,0,z)A(x,1,z)A
    2. Menunjukkan bahwa kita dapat flip jawaban ( x , 1 , z ) dari A untuk beberapa pilihan z tanpa mempengaruhi peluang diterima M oleh banyak.(x,1,z)AzM

    Memang, jika kita mulai dengan A dari langkah 1, probabilitas penerimaan M adalah nol. A tidak cukup memuaskan pilihan kedua dari janjinya, tetapi kita kemudian dapat membalik sedikit seperti pada langkah 2 dan itu akan. Sejak membalik bit menyebabkan M 's penerimaan probabilitas untuk tinggal mendekati nol, maka bahwa M tidak dapat secara bersamaan menerima x dan memenuhi R P janji.AMAMMxRP

Masih memperdebatkan dua langkah dalam Kasus 2:

  1. Perbaiki pilihan acak bit r untuk M . Sekarang mensimulasikan M menggunakan r sebagai keacakan dan menjawab pertanyaan sehingga ( x , 0 , z ) A dan ( x , 1 , z ) A . Perhatikan bahwa M membuat paling 2 n c queries. Karena ada 2 2 n c pilihan z , kita dapat memperbaiki pilihan unqueried dari z untuk memiliki ( xrMMr(x,0,z)A(x,1,z)AM2nc22nczz, 0 , z ) A , dan punya A masih memenuhi opsi pertama dari janjinya. Karena kami tidak dapat membuat Kasus 2 berfungsi untuk M , ini berarti M harus menolak semua pilihan keacakannya relatif terhadap A , dan khususnya pada r . Oleh karena itu jika kita memilih A untuk memiliki ( x , 0 , z ) A dan ( x , 1 , z ) A untuk setiap pilihan z(x,0,z)AA, Maka untuk setiap pilihan acak bit r , M menolak relatif terhadap A .

  2. Misalkan untuk setiap z , fraksi bit acak yang M query ( x , 1 , z ) setidaknya 1 / 2 . Maka jumlah total kueri setidaknya 2 2 n c 2 2 n c / 2 . Di sisi lain, M membuat paling banyak 2 2 n c 2 n c query di semua cabangnya, sebuah kontradiksi. Oleh karena itu ada pilihan z sehingga fraksi bit acak untuk yang Mkueri ( x , 1 , z ) kurang dari 1/2. Membalik nilai A pada string ini karena mempengaruhi peluang diterima M oleh kurang dari 1 / 2 .

Andrew Morgan
sumber
Jawaban ini cukup panjang dan mungkin akan mendapat manfaat dari tautan ke sumber daya luar yang memberikan penjelasan yang lebih baik tentang teknik yang terlibat. Jika ada yang tahu, saya akan dengan senang hati memasukkannya.
Andrew Morgan
Mungkin dalam survei Ko.
Kaveh
1
@ Kaveh: Saya melihat survei ini (yang Anda maksudkan, kan?), Tapi saya tidak melihat banyak hal yang sepertinya langsung relevan. Sebagian besar hasil tampak seperti mereka akan jatuh ke dalam kasus membuktikan B P PN P = R P . Satu poin penting adalah bahwa P = R P relatif terhadap oracle acak, dan jadi kita mendapatkan B P PN P = R P relatif terhadap oracle acak.
Andrew Morgan
-1

Tidak, tidak diketahui. Ini mungkin bukan bukti yang paling meyakinkan, tetapi lihat pencarian Google ini .

domotorp
sumber