NP significa tiempo polinomial no determinista.
Es mi primera pregunta en este sitio. Estoy tomando un curso de maestría en teoría de la computación. ¿Cómo explicarías el problema P = NP a un niño de 10 años y por qué tiene una recompensa monetaria? Su toma? Actualizaré la pregunta a medida que mi cabeza se aclare al...
A veces se afirma que la Teoría de la Complejidad Geométrica de Ketan Mulmuley es el único programa plausible para resolver las preguntas abiertas de la teoría de la complejidad como la pregunta P vs. NP. Ha habido varios comentarios positivos de famosos teóricos de la complejidad sobre el...
Estoy interesado en la generalización natural del famoso 15-rompecabezas , donde tienes que deslizar bloques hasta que hayas ordenado todos los números dados (generalmente hay un espacio de 1 bloque). Ahora la generalización sería extender el tamaño del rompecabezas de 15 a , donde un campo es...
Muchos expertos creen que la conjetura es cierta y la utilizan en sus resultados. Mi preocupación es que la complejidad depende en gran medida de la conjetura P ≠ N P.P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} Entonces mi pregunta es: Mientras no se pruebe la...
Es bien sabido por el teorema de Ladner que si , entonces existen infinitos problemas -intermediate ( ). También hay candidatos naturales para este estado, como Graph Isomorphism y varios otros, consulte Problemas entre P y NPC . Sin embargo, se sabe que la gran mayoría de la multitud de...
Se conjetura que ya que lo contrario implicaría \ mathsf {PH} = \ Sigma_2 . El teorema de Ladner establece que si \ mathsf {P} \ ne \ mathsf {NP} entonces \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset . Sin embargo, la prueba no parece generalizarse...
La pregunta sobre la teoría " ¿Qué es NP restringido a testigos de tamaño lineal? " Pregunta sobre la clase NP restringida a testigos de tamaño lineal , peroO ( n )O(n)O(n) ¿Existen problemas naturales de NP completo en los que (sí) las instancias de tamaño requieren testigos de tamaño mayor que...
¿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 =
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...
Peter Shor mostró que dos de los problemas NP-intermedios más importantes, la factorización y el problema de registro discreto, están en BQP. Por el contrario, el algoritmo cuántico más conocido para SAT (búsqueda de Grover) solo produce una mejora cuadrática sobre el algoritmo clásico, lo que...
Esta pregunta se migró de Computer Science Stack Exchange porque se puede responder en Teorematic Computer Science Stack Exchange. Migrado hace 6 años . Parece que muchas personas creen que , en parte porque creen que la factorización no es solucionable por tiempo
¿Hay un ejemplo de un idioma que está en , pero donde no podemos probar este hecho directamente al mostrar que existe un testigo polinómico para la membresía en este idioma?NPNPNP En cambio, el hecho de que el idioma está en se probaría reduciéndolo a otro idioma en , donde el vínculo entre los...
¿Hay algún problema natural en que no se sabe (se sabe que se cree) en ?NP∩coNPNP∩coNPNP \cap coNPUP∩coUPUP∩coUPUP \cap coUP Obviamente, el más grande que todos conocen en es la versión de decisión de factoring (no tiene un factor de tamaño como máximo k), pero eso es de hecho en .NP∩coNPNP∩coNPNP...
¿Esta respuesta a los principales problemas no resueltos en informática teórica? La pregunta indica que está abierto si un problema particular en NP requiere tiempo de .Ω(n2)Ω(n2)\Omega(n^2) Mirar los comentarios a continuación me hizo preguntarme: Además del relleno y trucos similares, ¿cuál...
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...
¿Existe un lenguaje NP (preferiblemente natural) completo , de modo que por cada n ≥ 1 | L ∩ { 0 , 1 } n | = 2 n - 1 retenciones? En otras palabras, L contiene precisamente la mitad de todas las instancias de n bits.L ⊆ { 0 , 1 }∗L⊆{0,1}∗L\subseteq \{0,1\}^*n ≥ 1n≥1n\geq 1 El | L∩{0,1 }norteEl | =...
Esto está relacionado con la pregunta ¿Ya se conoce el tamaño de membresía de los testigos para cada idioma de NP? Algunos problemas naturales (-completos) tienen testigos de longitud lineal: una asignación satisfactoria para , una secuencia de vértices para , etc. S A T H A M P A T...
El acceso a un oráculo proporcionaría una mayor aceleración súper polinomial para todo en (suponiendo que el conjunto no esté vacío). Sin embargo, está menos claro cuánto se beneficiaría de este acceso al oráculo. Por supuesto, la aceleración en no puede ser superpolinomial, pero aún puede ser...
Esta es una especie de pregunta abierta, por lo que me disculpo de antemano. ¿Hay ejemplos de afirmaciones que (aparentemente) no tienen nada que ver con la complejidad o las máquinas de Turing, pero la respuesta implicaría ?P≠NPP≠NP\mathbf{P}\neq
Estaba leyendo " ¿Es P versus NP formalmente independiente? ", Pero me desconcertó. Se cree ampliamente en la teoría de la complejidad que . Mi pregunta es sobre qué pasa si esto no es demostrable (digamos en ). (Supongamos que solo descubrimos que es independiente de pero no hay más información...