Una pregunta reciente de Huck Bennett sobre si la clase PH estaba contenida en la clase PP, recibió respuestas algo contradictorias (todo es cierto, parece). Por un lado, se dieron varios resultados de oráculo en sentido contrario, y por otro Scott sugirió que la respuesta es probablemente positiva...
En muchos dominios, hay técnicas canónicas que todos los que trabajan en el campo deben dominar. Por ejemplo, para las reducciones de espacio de registro, el "truco de bits" para la composición que consiste en no construir la salida completa de la función compuesta, pero siempre solicita volver a...
¿Hay ejemplos de juguetes que brinden información 'esencial' para comprender las tres barreras conocidas para el problema : relativización, pruebas naturales y algebrización?PAGS= NPAGSP=NPP =
Estaba leyendo el artículo de Andrej Bauer, Primeros pasos en la teoría sintética de la computabilidad . En la conclusión, señala que Nuestra axiomatización tiene su límite: no puede probar ningún resultado en la teoría de computabilidad que no se relativice con los cálculos de oráculo. Esto es...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
IP = PSPACE aparece como el ejemplo canónico de un resultado no relativizante, y la prueba de esto es que existe un oráculo tal que , mientras que {\ sf CONP} ^ O \ subseteq {\ sf PSPACE} ^ O para todos los oráculos O .c o N P O ⊈ I P O c o N P O ⊆ P S P A C E O OOOOc o N PO⊈ I...
Antecedentes Se sabe que existe un oráculo AAA tal que, P S P A C E A ≠ P H APSPACEA≠PHAPSPACE^A \neq PH^A . Incluso se sabe que la separación es relativa a un oráculo aleatorio. Informalmente, uno puede interpretar que esto significa que hay muchos oráculos para los cuales P S P A C...
¿Cuáles son algunos ejemplos de pares de clases de complejidad y B tales queAAABBB no sabemos si , yA=BA=BA=B tampoco conocemos relativizaciones contradictorias (es decir, no conocemos los oráculos y Q de manera que A P = B P y A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P = B^PAQ≠BQAQ≠BQA^Q \ne B^Q Para...
Este es un seguimiento de esta pregunta y está relacionado con esta pregunta de Shiva Kinali. Parece que las pruebas en estos documentos ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) usan teoremas de jerarquía. Quiero saber si las pruebas son teoremas de diagonalización " pura...
El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...
Lance Fortnow afirmó recientemente que probar L! = NP debería ser más fácil que probar P! = NP : Separar NP del espacio logarítmico. Di cuatro enfoques en una encuesta previa al blog de 2001 sobre la diagonalización (Sección 3), aunque ninguno ha funcionado. Debería ser mucho más fácil que...
Según tengo entendido, una prueba de que P = NP o P ≠ NP debería ser no relativizable (como en los oráculos de la teoría de la recursión). Sin embargo, prácticamente todas las pruebas parecen ser relativizables. ¿Cuáles son buenos ejemplos de pruebas no relativizables, del tipo que una prueba P =...
¿Es posible demostrar que una oración debe ser formalmente independiente basada en el hecho de que no es relativizante? En otras palabras, ¿hay ejemplos de oraciones en la teoría de la computabilidad / complejidad donde se pueda demostrar tanto a) que todas las pruebas que resuelven la cuestión de...
NL⊈PNL⊈P\mathsf{NL} \nsubseteq \mathsf{P} Consideremos ahora las familias de circuitos con puertas de Oracle - por ejemplo, , donde es una clase de la complejidad del circuito que contiene logspace con acceso a Oracle a otra clase , a través de puertas de Oracle adjuntas a la base de . ¿Hay algún...
No recuerdo haber visto una separación de clases no basada en resultados de diagonalización y relativización. La diagonalización aún podría usarse para separar las clases conocidas restantes, porque los argumentos no relativizantes aún podrían usarse en la conclusión de diagonalización, o en la...
Me gustaría saber si existe un mundo donde relativizada . También estoy interesado en saber si existe un mundo donde relativizada P B ≠ N P B = P P B .PAGUNA= N PUNA≠ P PUNAPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}PAGsi≠ N Psi= P PsiPB≠NPB=PPB{\bf P^B} \not = {\bf NP^B} = {\bf...
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...
Deje que sea un problema completo de EXP. Entonces, .AAAPA=NPAPA=NPAP^A = NP^A Deje que sea cierto oráculo que tiene en cuentas las consultas que (TM en P) hará, y podemos obtener .BBBP B ≠ N P BMMMPB≠NPBPB≠NPBP^B \neq NP^B Pregunta: ¿Tenemos resultados de oráculo similares para P vs...
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
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...