Clases de complejidad computacional y sus relaciones.
Norbert Blum publicó recientemente una prueba de 38 páginas de que . ¿Es correcto?PAGS≠ NPAGSP≠NPP \ne NP También sobre el tema: ¿dónde más (en Internet) se está discutiendo su corrección? Nota: el enfoque de este texto de pregunta ha cambiado con el tiempo. Vea los comentarios de las preguntas...
Esta pregunta es algo que me he preguntado por un tiempo. Cuando las personas describen el problema P vs. NP, a menudo comparan la clase NP con la creatividad. Señalan que componer una sinfonía de calidad de Mozart (análoga a una tarea de NP) parece mucho más difícil que verificar que una sinfonía...
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 L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} y que L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , donde L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . También sabemos que...
Según tengo entendido, el programa de teoría de la complejidad geométrica intenta separar al demostrar que el funcionamiento de una matriz de valores complejos es mucho más difícil de calcular que el determinante.VP≠VNPVP≠VNPVP \neq VNP La pregunta que tuve después de hojear los documentos de GCT:...
La clase de complejidad consiste en esos problemas que pueden decidirse por una máquina de Turing no determinista de tiempo polinomial que tiene como máximo una ruta computacional de aceptación. Es decir, la solución, si la hay, es única en este sentido. Se cree altamente improbable que todos los...
La complejidad cada vez mayor de los programas de computadora y la posición cada vez más crucial que tienen las computadoras en nuestra sociedad me hacen preguntarme por qué todavía no usamos colectivamente lenguajes de programación en los que tenga que dar una prueba formal de que su código...
En la introducción y explicación, las clases de complejidad P y NP a menudo se dan a través de la máquina Turing. Uno de los modelos de computación es el cálculo lambda. Entiendo que todos los modelos de computación son equivalentes (y si podemos introducir algo en términos de máquina de Turing,...
En su libro "Complejidad computacional", Papadimitriou escribe: RP es, en cierto sentido, un tipo nuevo e inusual de clase de complejidad. Ninguna máquina de Turing no determinista limitada polinómicamente puede ser la base para definir un lenguaje en RP. Para que una máquina N defina un...
Desde el punto de sentido común de vista, es fácil creer que la adición de no determinismo a se extiende significativamente su potencia, es decir, N P es mucho mayor que P . Después de todo, el no determinismo permite el paralelismo exponencial, que sin duda parece muy poderoso....
Considere el siguiente problema de conteo (o el problema de decisión asociado): dados dos enteros positivos codificados en binario, calcule su máximo divisor común (mcd). ¿Cuál es la clase de complejidad más pequeña en la que se encuentra este problema? ¿Me puede proporcionar una referencia? En...
Como aficionado de TCS, estoy leyendo material muy introductorio sobre informática cuántica. Aquí están los pocos datos elementales que he aprendido hasta ahora: No se sabe que las computadoras cuánticas resuelvan problemas NP-completos en tiempo polinómico. "La magia cuántica no será suficiente"...
El problema central de la teoría de la complejidad es posiblemente vs .PAGSPAGSPnortePAGSnortePAGSNP Sin embargo, dado que la naturaleza es cuántica, parecería más natural considerar las clases (es decir, problemas de decisión que una computadora cuántica puede resolver en tiempo polinómico, con...
Esta pregunta trata sobre problemas para los cuales existe una gran brecha de complejidad abierta entre el límite inferior conocido y el límite superior, pero no debido a problemas abiertos en las propias clases de complejidad. Para ser más precisos, digamos que un problema tiene clases de brecha...
En el artículo The Random Oracle Hypothesis Is False , los autores (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan y Rohatgi) discuten las implicaciones de la hipótesis del oráculo aleatorio . Argumentan que sabemos muy poco acerca de las separaciones entre clases de complejidad, y la mayoría de...
A menudo se cita una justificación filosófica para creer que P! = NP incluso sin pruebas. Otras clases de complejidad tienen evidencia de que son distintas, porque si no, habría consecuencias "sorprendentes" (como el colapso de la jerarquía polinómica). Mi pregunta es, ¿cuál es la base para creer...
Existen toneladas de problemas NP-completos y fuentes que los recopilan, por ejemplo, vea el libro de Garey y Johnson. Me interesaría ver una lista de problemas NEXP-complete también. ¿Hay uno disponible? Como supongo que no hay, abro esta pregunta (¿se supone que es una wiki comunitaria? No sé...
¿Cuáles serían las desagradables consecuencias de NP = PSPACE? Me sorprende no haber encontrado nada sobre esto, dado que estas clases se encuentran entre las más famosas. En particular, ¿tendría alguna consecuencia en las clases
Suponga que P = NP es verdadero. ¿Habría alguna aplicación práctica para construir una computadora cuántica, como resolver ciertos problemas más rápido, o cualquier mejora sería irrelevante debido al hecho de que P = NP es cierto? ¿Cómo caracterizaría la mejora en la eficiencia que se produciría si...
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...