En Complejidad descriptiva , Immerman tiene Corolario 7.23. Las siguientes condiciones son equivalentes: 1. P = NP. 2. Sobre estructuras finitas, ordenadas, FO (LFP) = SO. Esto puede considerarse como "amplificación" de P = NP a un enunciado equivalente sobre (presumiblemente) clases de...
Sabemos que el primer nivel de la jerarquía polinómica (es decir, NP y co-NP) está en PP, y que . También sabemos por el teorema de Toda que .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} ¿Sabemos si ? Si no, ¿por qué es que con un oráculo de es más fuerte que ? ¿Es posible...
Editar : como Ravi Boppana señaló correctamente en su respuesta y Scott Aaronson también agregó otro ejemplo en su respuesta , la respuesta a esta pregunta resultó ser "sí" de una manera que no esperaba en absoluto. Primero pensé que no respondían la pregunta que quería hacer, pero después de...
¿Es cierto que hay problemas en la jerarquía polinómica que se pueden resolver en el tiempo (por una máquina de Turing alterna en algún nivel de la jerarquía polinómica) que no se pueden resolver en O ( n k - 1 ) en ningún nivel de jerarquía polinómica? En otras palabras, ¿existe un teorema de...
Es bien sabido que si P=NPP=NP\mathbf{P}=\mathbf{NP} entonces la jerarquía polinomio colapsa y P=PHP=PH\mathbf{P}=\mathbf{PH} . Esto puede entenderse fácilmente inductivamente utilizando máquinas Oracle. La pregunta es: ¿por qué no podemos continuar el proceso inductivo más allá de un nivel...
Necesito una lista de idiomas completos. Hay dos de estos problemas enumerados en el Complejo Zoo , a saber:Σpag2Σ2pag\Sigma_2^p Mínimo equivalente DNF. Dada una fórmula DNF F y un entero k, ¿hay una fórmula DNF equivalente a F con k o menos ocurrencias de literales? El implicante más corto. Dada...
Sabemos que si entonces todo el PH colapsa. ¿Qué pasa si la jerarquía polinómica se colapsa parcialmente? (¿O cómo entender que el PH podría colapsar por encima de cierto punto y no por debajo?)PAG= NPAGP=NPP=NP En palabras más cortas, ¿cuáles serían las consecuencias de y P ≠ N P ?nortePAG= c o...
Contenidos entre cada nivel de la jerarquía polinómica hay varias clases de complejidad, que incluyen , DP , BH k y Σ P i ∩ Π P i . Por falta de una mejor terminología, me referiré a estas y a otras como clases intermedias entre los niveles i e i + 1 en la jerarquía polinómica. Para los propósitos...
Se sabe que agregar aleatorización de error limitado a PSPACE no agrega potencia. Es decir, BPPSAPCE = PSPACE. Se desconoce si P = BPP, pero se sabe que .B PPAG⊆ Σ2∩ Π2BPP⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Por lo tanto, es posible (mientras se conjetura que es falso) que agregar probabilidad a...
El teorema de PCP establece que cada problema de decisión en NP tiene pruebas probabilísticamente comprobables (o de manera equivalente, que existe un sistema de prueba completo y cuasi-sonoro para teoremas en NP que usa complejidad de consulta constante y logarítmicamente muchos bits...
La siguiente noción de un algoritmo de destilación proviene de "En problemas sin núcleos polinomiales". Deje que se le dé una lenguaUn algoritmo de destilación para toma una lista dada de cadenas de entrada y calcula una cadena de salida tal que:L { x i } i ∈ [ t ] yLLLLLL{ xyo}i ∈ [ t...
Conozco las siguientes variantes de problemas SUBSETSUM: ( Elberfeld at. Al., 2010 ), NP-complete , y NEXP-complete ( enlace ).S U B S E T S U M S U C C I N C T - S U B S E T S U MUN A R Y - S UB S E T S UM∈LUNARY-SUBSETSUM∈L \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} SUBSETSUMETROSUBSETSUM...
Las versiones no uniformes de P, NP y coNP son P / poly, NP / poly y coNP / poly. Del mismo modo, podemos definir una versión no uniforme para cada nivel en el PH. Por ejemplo: / poly consiste en problemas de la forma , donde C es un circuito de tamaño polinómico que puede variar según la longitud...