BPP上限

Question

$ bpp subseteq p^{np} $は？それは合理的に思えますが、これの証拠があるかどうかはわかりません！

Answer 1

$ mathsf {bpp} subseteq mathsf {p}^{ mathsf {np}} $。

現在私たちが$ mathsf {bpp} $について言うことができる最高のことは、それが含まれていることです s₂p, 、$ sigma_2 cap pi_2 $および$ mathsf {zpp}^{ mathsf {np}} $に含まれるクラス。ウィキペディアでの参照を参照してください。

$ mathsf {bpp} subseteq mathsf {p}^{ mathsf {np}} $の場合、この事実は相対的ではありません（stockmeyer、 #Pの近似アルゴリズムについて).