Muchos creen que BPP=P⊆NPBPP=P⊆NP\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP} . Sin embargo, solo sabemos que BPPBPP\mathsf{BPP} está en el segundo nivel de jerarquía polinómica, es decir, BPP⊆ΣP2∩ΠP2BPP⊆Σ2P∩Π2P\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2 . Un paso hacia la...
¿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 =
Es bien sabido que cualquier prueba que resuelva la cuestión P vs NP debe superar la relativización , las pruebas naturales y las barreras de algebrización . El siguiente diagrama divide el "espacio de prueba" en diferentes regiones. Por ejemplo, RNRNRN corresponde al conjunto de pruebas que se...
Recientemente, Ryan Willams demostró que la constructividad en la prueba natural es inevitable para derivar una separación de clases de complejidad: y . NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} La constructividad en la prueba natural es una condición que satisface todas las pruebas combinatorias...
La redacción exacta del título se debe a Anand Kulkarni (quien propuso que se creara este sitio). Esta pregunta se hizo como una pregunta de ejemplo, pero tengo una curiosidad increíble. Sé muy poco acerca de la geometría algebraica y, de hecho, solo tengo una comprensión superficial y de pregrado...
Las pruebas naturales son una barrera para probar los límites inferiores de la complejidad del circuito de las funciones booleanas. Ellos no implican directamente cualquier barrera en probar límites inferiores en el la complejidad del circuito. ¿Hay algún progreso hacia la identificación de tales...
Todos sabemos que mostrar tiene barreras. Todos hemos estudiado estas barreras porque creemos que .PAG≠ NPAGPAG≠nortePAGP\ne NPPAG≠ NPAGPAG≠nortePAGP\ne NP Sin embargo, suponga y hay personas sabias que creen que existe la posibilidad . Si este es realmente el caso, el hecho de que no hayamos...
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...
Este es un seguimiento de mi pregunta anterior: Mejor complejidad de tiempo determinista conocida límite inferior para un problema natural en NP Me resulta desconcertante que no hayamos podido probar ningún límite inferior de tiempo determinista cuadrático para ningún problema interesante de NP...
¿ Las pruebas naturales , la relativización y la algebrización también afectan la separación de otras clases de complejidad como etc.?L ≠ NL ≠ NPAGS≠ c o NPAGS≠ PH≠ PSPAGSA CmiL≠NL≠NP≠coNP≠PH≠PSPACEL\neq NL\neq NP\neq coNP \neq PH\neq PSPACE Por ejemplo, la barrera de pruebas naturales debería...