Les générateurs invulnérables sont définis comme suit: Soit une relation NP, et M une machine qui accepte L ( R ) . Informellement, un programme est un générateur invulnérable si, sur l'entrée 1 n , il produit des paires instance-témoin ( x , w ) ∈ R , avec | x | = N , selon une répartition en...
La plupart de la littérature semble s'intéresser aux machines à oracles simples pour des problèmes spécifiques, mais il semble y avoir quelques articles qui considèrent les machines à oracles multiples. Existe-t-il un bon article ou une thèse qui donne un aperçu de ce que l'on sait de ces machines?...
J'ai pensé à la question suivante à plusieurs reprises depuis que j'ai vu cette question sur la cryptographie . Question Soit une relation TFNP . Un oracle aléatoire peut-il aider P / poly à casser avec une probabilité non négligeable? Plus formellement, \ newcommand {\ Pr} {\ operatorname {Pr}} \...