Preguntas sobre o relacionadas con P vs. NP
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...
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...
¿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 =
¿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...
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...
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
¿Existe un ejemplo explícito conocido de un algoritmo con la propiedad tal que si PAG≠ NPAGPAG≠nortePAGP\neq NP este algoritmo no se ejecuta en tiempo polinomial y si PAG= NPAGPAG=nortePAGP=NP se ejecuta en tiempo
La famosa conjetura del isomorfismo de Berman y Hartmanis dice que todos los lenguajes completos son polinomiales en tiempo isomorfo (p-isomorfo) entre sí. El significado clave de la conjetura es que implica . Fue publicado en 1977, y una evidencia de apoyo fue que todos los completos de conocidos...
¿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...
Estoy interesado en aprender conexiones entre el "caos" o, más ampliamente, los sistemas dinámicos y la pregunta Aquí hay un ejemplo del tipo de literatura que estoy buscando:PAG= NPAGPAG=nortePAGP{=}NP Ercsey-Ravasz, Mária y Zoltán Toroczkai. "La dureza de la optimización como caos transitorio...
Creo que sería una buena idea hacer una lista de teoremas que indiquen que P no es igual a NP si y solo si tales y tales salidas, alguna clase de complejidad está contenida en otra clase de complejidad y así sucesivamente.
Gowers ha esbozado recientemente un problema, que él llama "determinación Borel discreta", cuya solución está relacionada con probar los límites inferiores del circuito. ¿Puede proporcionar un resumen del enfoque que se adapta a una audiencia de teóricos de la complejidad? ¿Qué se necesitaría...
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...
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 =...
en 1979 Hopcroft / Ullman escribió que L ⊆ P ⊆ NP ⊆ PSpace es conocido, pero L ⊊ PSpace es la única contención adecuada (y trivial) conocida, aunque se conjetura que todas son contenciones adecuadas, y "donde las cosas siguen en pie" ~ 4 décadas después . desde entonces, ¿hay alguna conexión...
La siguiente pregunta utiliza ideas de criptografía aplicadas a la teoría de la complejidad. Dicho esto, es una pregunta puramente teórica de la complejidad, y no se requiere ningún conocimiento criptográfico para responderla. Deliberadamente escribo esta pregunta de manera informal. A falta de...