Pour un oracle aléatoire R, BPP est-il égal à l'ensemble des langages calculables dans P ^ R?
Eh bien, le titre dit à peu près tout. La question intéressante ci-dessus a été posée par le commentateur Jay sur mon blog (voir ici et ici ). J'imagine à la fois que la réponse est oui et qu'il existe une preuve relativement simple, mais je ne pouvais pas la voir à la légère. (Très grossièrement,...