Apa buktinya ada ?

Apa buktinya ada ?$coRP \neq NP$

$coRP$ adalah kelas bahasa yang terdapat Mesin Turing probabililistik yang berjalan dalam waktu polinomial dan selalu menjawab Ya pada input milik bahasa dan jawaban TIDAK dengan probabilitas setidaknya satu setengah pada input yang bukan milik bahasa.

Ketika mempertimbangkan kekuatan non-determinisme (P vs NP), pengacakan tampaknya seperti masalah urutan ke-2. Khususnya ketika kita berpikir tentang "P = NP?" kami benar-benar tertarik dengan pertanyaan "apakah semua masalah NP dapat ditelusuri", di mana pengacakan dapat diizinkan, sehingga penertelusuran benar-benar berarti "dalam BPP". Jadi "NP yang terkandung dalam BPP" tampaknya pada dasarnya tidak mungkin seperti "P = NP", dan pada kenyataannya jika ini dianggap berbeda maka orang akan peduli tentang yang pertama daripada yang terakhir. (Varian aneh "NP in coRP" secara formal di suatu tempat di tengah antara keduanya, tetapi secara konseptual pada dasarnya sama). Jika ada generator pseudo acak yang cukup bagus maka kedua pertanyaan secara formal sama. Demikian pula, dalam "pengaturan tidak seragam" pengacakan diketahui tidak membantu dan dengan demikian "

Jika dengan coR yang Anda maksud adalah coRP, maka diyakini oleh banyak orang bahwa P = RP = coRP = BPP, dan juga bahwa P tidak sama dengan NP, maka coRP tidak sama dengan NP.

Lebih langsung, jika NP sama dengan coRP, maka itu akan terkandung dalam coNP (karena coRP terkandung dalam coNP). Kemudian dengan simetri, NP = coNP. Ini akan menyiratkan bahwa hierarki polinomial runtuh ke tingkat pertama. Namun, secara luas diyakini bahwa hierarki polinom adalah tak terbatas.

Hanya untuk menghindari diskusi duplikat dari topik yang sama, ini sangat terkait dengan pertanyaan sebelumnya:

Apa bukti spesifik yang ada untuk P = RP?

Singkatnya, P = BPP mengikuti asumsi kekerasan, dan P = BPP menyiratkan P = coRP.