Konsekuensi

Banyak yang percaya bahwa . Namun kita hanya tahu bahwa B P P berada pada tingkat kedua hierarki polinomial, yaitu B P P ⊆ Σ P 2 ∩ Π P 2 . Langkah menuju menunjukkan B P P = P adalah untuk pertama membawanya ke tingkat pertama dari hirarki polinomial, yaitu B P P ⊆ N P .$\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$$\mathsf{BPP}$$\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$$\mathsf{BPP} = \mathsf{P}$$\mathsf{BPP} \subseteq \mathsf{NP}$

Penahanannya akan berarti bahwa nondeterminisme setidaknya sekuat keacakan untuk waktu polinomial.

Ini juga berarti bahwa jika untuk suatu masalah kita dapat menemukan jawaban menggunakan algoritma acak yang efisien (waktu polinomial) maka kita dapat memverifikasi jawaban secara efisien (dalam waktu polinomial).

Adakah konsekuensi menarik yang diketahui untuk ?$\mathsf{BPP} \subseteq \mathsf{NP}$

Apakah ada alasan untuk percaya bahwa membuktikan di luar jangkauan sekarang (misalnya hambatan atau argumen lain)?$\mathsf{BPP} \subseteq \mathsf{NP}$

Untuk satu, membuktikan akan dengan mudah menyiratkan bahwa N E X P ≠ B P P , yang sudah berarti bahwa bukti Anda tidak dapat direlatifikasi.$BPP \subseteq NP$$NEXP \neq BPP$

$coRP \subseteq NTIME[2^{n^{o(1)}}]$$NEXP \not\subset P/poly$

Saya pribadi tidak tahu mengapa itu terlihat "di luar jangkauan" tetapi tampaknya sulit untuk dibuktikan. Tentu saja beberapa trik yang benar-benar baru diperlukan untuk membuktikannya.