Nuevos trabajos más importantes en complejidad computacional

34

A menudo escuchamos sobre investigaciones clásicas y publicaciones en el campo de la complejidad computacional (Turing, Cook, Karp, Hartmanis, Razborov, etc.). Me preguntaba si hay documentos publicados recientemente considerados fundamentales y una lectura obligada. Por reciente quiero decir en los últimos 5/10 años.

Yamar69
fuente

Respuestas:

28

El reciente artículo de László Babai que muestra que Graph Isomorphism está en Cuasi-P ya es un clásico.

Aquí hay una exposición más accesible del resultado publicado en los procedimientos de ICM 2018.

Denis
fuente
3
¿Se considera este documento completamente examinado por la comunidad? El sitio web de Laci todavía dice que no está completamente revisado por pares, pero su última actualización fue hace más de un año.
Stella Biderman
66
@StellaBiderman Incluso tenemos una pregunta por separado sobre eso: cstheory.stackexchange.com/q/40353 .
Emil Jeřábek apoya a Monica el
25

En una preimpresión reciente, Harvey y Van Der Hoeven muestran cómo calcular la multiplicación de enteros en el tiempo O(nlogn) en una máquina Turing de varias cintas, culminando unos 60 años de investigación (Karatsuba, Toom – Cook, Schönhage – Strassen, Fürer , Harvey – Van Der Hoeven – Lecerf). El documento aún no ha sido revisado por pares, pero el trabajo previo de los autores sobre este problema lo hace plausible, y los expertos parecen ser optimistas.

Emil Jeřábek apoya a Monica
fuente
22

La importancia está en los ojos del espectador. Sin embargo, diría que la conjetura de dicotomía CSP Feder-Vardi, demostrada independientemente por A. Bulatov y D. Zhuk , es un resultado fundamental.

Emil Jeřábek apoya a Monica
fuente
2
Estos son documentos realmente importantes y definitivamente pertenecen a esta lista, pero forman la piedra angular en un gran cuerpo de trabajo. No estoy seguro de que este logro abra muchas más áreas de investigación (lo que esperaría de un resultado "seminal"). Creo que el trabajo fundamental aquí fue el documento original de Feder-Vardi.
András Salamon
1
El OP utiliza algunos términos diferentes: "Más importante", "Seminal" y "Debe leer". La prueba de la conjetura de la dicotomía probablemente satisface la primera (¡es un resultado fascinante y poderoso!) Pero no la segunda (como dijiste, esta prueba en sí misma no cambiará sustancialmente la forma en que avanza la investigación) o la tercera (la prueba está suficientemente lejos de las implicaciones de la conjetura, ya que es probable que no sea interesante a menos que ya estés en ese subcampo.)
Alex Meiburg
16

Este nuevo artículo de Hao Huang [1] (aún no revisado por pares, que yo sepa) probablemente califica ... demuestra la conjetura de sensibilidad de Nisan y Szegedy, que ha estado abierto durante ~ 30 años.

[1] Subgrafos inducidos de hipercubos y una prueba de la Conjetura de la sensibilidad, Hao Huang. Manuscrito, 2019. https://arxiv.org/abs/1907.00847

Clemente C.
fuente
2
Si bien el documento no ha sido oficialmente revisado por pares, es bastante claro. Es uno de los mejores ejemplos de una prueba "NP" que es increíblemente fácil de verificar y bastante difícil de encontrar.
Stella Biderman
2
@StellaBiderman Lo sé, y estoy de acuerdo. Pero aún es importante decirlo, ya que la revisión por pares es más o menos la moneda en la que basamos nuestro sistema.
Clemente C.
14

El trabajo de 2018 de Subhash Khot, Dor Minzer y Muli Safra "Los conjuntos pseudoaleatorios en Grassmann Graph tienen una expansión casi perfecta" nos ha conseguido "a mitad de camino" a la Conjetura de los juegos únicos y es metodológicamente bastante interesante según personas más conocedoras que yo. Citando a Boaz Barak ,

Esto establece por primera vez la dureza de los juegos únicos en el régimen para el que se conocía un algoritmo de tiempo sub-exponencial, y por lo tanto (necesariamente) usa una reducción con alguna explosión polinómica (grande). Si bien en teoría todavía es posible que la conjetura de los juegos únicos sea falsa (como personalmente creí que sería el caso hasta esta última secuencia de resultados), el escenario más probable es ahora que el UGC es verdadero y la complejidad del UG (s , c) el problema se parece a lo siguiente ...

El documento ha causado que algunos investigadores (incluido Barak) cambien públicamente su opinión sobre la verdad de la UGC (de falsa a verdadera).

Stella Biderman
fuente
13

"Sobre la posibilidad de algoritmos SAT más rápidos" por Pătraşcu & Williams (SODA 2010). Da relaciones estrechas entre la complejidad de resolver CNF-SAT y la complejidad de algunos problemas polinomiales (conjunto dominante de k, suma d, etc.).

Los resultados son dobles: podemos mejorar la complejidad de resolver algunos problemas polinómicos y, por lo tanto, ETH es falso y obtenemos un mejor algoritmo para CNF-SAT. O ETH es cierto y, por lo tanto, obtenemos límites más bajos en varios problemas polinómicos.

El documento es sorprendentemente fácil de leer y entender. Para mí, es el comienzo real de la complejidad de grano fino.

Lamina
fuente
9

Es un año más allá del límite de 10 años, pero "Delegar la computación: pruebas interactivas para muggles" de Goldwasser, Kalai y Rothblum ha sido un artículo muy influyente. El resultado principal es que hay una prueba interactiva para cualquier computación uniforme en el espacio logarítmico donde el probador se ejecuta en tiempo poly (n) y el verificador en tiempo n * polylog (n) con bits de comunicación polylog (n).

El documento ha iniciado la investigación sobre pruebas interactivas y el cálculo verificable de problemas en P ha sido increíblemente influyente en la criptografía, donde el trabajo que siguió ha hecho que las pruebas interactivas del mundo real sean casi prácticas.

Stella Biderman
fuente
@ Sasho No estoy en desacuerdo. Sin embargo, este documento no trata realmente sobre la optimización del tiempo de ejecución. El hecho de que en el mundo real se ejecute mucho más rápido que los enfoques anteriores es un beneficio, pero no es fundamental para el documento (y en realidad no es medido por los autores). Es FGC porque se ve en la fuente de verificación de los verificadores más débiles que P .
Stella Biderman
4

Para el impacto, y alcanzar el papel de referencia de Indyk, y Backurs que dan límites para editar el cálculo de distancia. Este documento muestra los límites de la informática, mediante enlaces, k-SAT y SETH. Para limitar el cálculo de la distancia levenshtein, entre cadenas, el papel muestra límites estrechos para calcular la distancia de edición, mejor que violar SETH (SETH puede ser falso en primer lugar, o incluso tener límites inferiores más estrictos ). La aplicabilidad de SETH a posibles problemas en P, para obtener límites o limitar la aplicación de algoritmos (¡posiblemente computación!) Es nueva.

O este artículo de P. Goldberg y C. Papadimitrou, sobre una complejidad uniforme para funciones totales Hacia una teoría de complejidad unificada de funciones totales .

usuario3483902
fuente
2

No estoy seguro de si esto califica, ya que tiene más de 10 años y no es realmente un resultado de complejidad computacional en sí mismo, pero creo que vale la pena señalar el par de {Teorema de estructura gráfica, Teorema de gráfico menor}. Se completó en 2004 y establece una equivalencia entre "Complejidad topológica limitada" y "No contiene un conjunto finito de menores". Cada teorema establece una dirección de la equivalencia.

Esto ha tenido principalmente un impacto en el ámbito de la teoría de la complejidad parametrizada, donde una de estas medidas a menudo está limitada, lo que permite algoritmos eficientes que aprovechan la otra. Entonces, diría que estos resultados han tenido un impacto sustancial en la complejidad computacional, incluso si no provienen directamente de ese campo.

Alex Meiburg
fuente