Los generadores invulnerables se definen de la siguiente manera: Sea una relación NP y M una máquina que acepte L ( R ) . Informalmente, un programa es un generador invulnerable si, en la entrada 1 n , produce pares de instancia-testigo ( x , w ) ∈ R , con | x | = n , de acuerdo con una...
La mayor parte de la literatura parece estar relacionada con máquinas con oráculos individuales para problemas específicos, sin embargo, parece haber algunos documentos que consideran máquinas con oráculos múltiples. ¿Existe un buen trabajo o tesis que proporcione una visión general de lo que se...
He estado pensando en la siguiente pregunta en varias ocasiones desde que vi esta pregunta sobre Criptografía . Pregunta Sea RRR una relación TFNP . ¿Puede un oráculo aleatorio ayudar a P / poly a romper RRR con una probabilidad no despreciable? Más
Según BGS teorema [1], no es un oráculo de tal manera que .P A ≠ N P AUNAUNAAPAGSUNA≠ NPAGSUNAPAGSUNA≠nortePAGSUNAP^A\neq NP^A Si la operación de relativización fuera una función bien definida, uno esperaría que de se pudiera concluir que , por ejemplo, seguiría de BGS. Sin embargo, todavía está...
En el artículo Relativizaciones de la P =? Pregunta NP , Baker et al. demostró que existen mundos relativizados en los que se mantiene P = NP o P ≠ NP. Todos los oráculos en su configuración eran conjuntos recursivos. En otro artículo relativo a un Oráculo aleatorio , P A ≠ N P A ≠ co- N P A con...
Antecedentes Sabemos que .P#P⊆PSPACEP#P⊆PSPACEP^{\#P} \subseteq PSPACE Además, se conoce a partir del teorema de Toda que .PH⊆P#PPH⊆P#PPH \subseteq P^{\#P} Para obtener más información sobre , consulte aquí: https://en.wikipedia.org/wiki/Sharp-P#P#P\#P Pregunta ¿Existe un oráculo...