Resultados sorprendentes en la complejidad (no en la lista de blogs de complejidad)

¿Cuáles fueron los resultados más sorprendentes en complejidad?

Creo que sería útil tener una lista de resultados inesperados / sorprendentes. Esto incluye resultados que fueron sorprendentes y surgieron de la nada y también resultados que resultaron diferentes de lo que la gente esperaba.

Editar : dada la lista de Gasarch, Lewis y Ladner en el blog de complejidad (señalado por @Zeyu), centremos esta wiki comunitaria en resultados que no están en su lista. Quizás esto conduzca a un enfoque en los resultados después de 2005 (según la sugerencia de @ Jukka).

Un ejemplo: Aprendizaje débil = Aprendizaje fuerte [Schapire 1990] : (¿Sorprendentemente?) Tener alguna ventaja sobre las conjeturas aleatorias te hace aprender PAC. Conduce al algoritmo AdaBoost.

Aquí está la publicación invitada de Bill Gasarch con la ayuda de Harry Lewis y Richard Ladner: http://blog.computationalcomplexity.org/2005/12/surprising-results.html

Si , entonces hay una prueba de "diagonalización" para ello.$P \neq NP$

Este resultado se debe a Kozen. No todos están de acuerdo con lo que él llama una prueba de "diagonalización".

En Barriers I, un panel de destacados teóricos de la complejidad acordó que el Teorema de Barrington fue el resultado que más los sorprendió. Fortnow explica el teorema de Barrington aquí: http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html

$NL$

Diría que el trabajo reciente de Jain, Upadhyay y Watrous muestra que QIP = IP = PSPACE es bastante sorprendente. Mi opinión es que no es tanto que QIP = IP sea interesante, sino más bien el hecho de que todo QIP se puede simular en una prueba cuántica interactiva de 3 rondas. Una demostración bastante genial del poder del paralelismo cuántico.

Algo que sigue sorprendiéndome es que es probable que BPP sea P: plantea muchas preguntas filosóficas sobre la naturaleza de la aleatoriedad.

Teoremas de incompletitud de Gödel

Teorema de las pruebas naturales de Razborov-Rudich.

(AFAIK) La gente tenía muchas esperanzas de probar los límites inferiores del circuito, pero después de este teorema, muchos dejaron de funcionar y pasaron a otros temas.

La versión de conteo del problema Monotone-SAT es # P-complete.

Una instancia Monotone-SAT es una fórmula proposicional $F$ con la siguiente restricción: cada variable siempre ocurre positiva o siempre negativa (en otras palabras, cada literal en $F$ es un literal puro).

Me sorprendió mucho este resultado, porque la versión de decisión del problema Monotone-SAT es trivial.

Es ampliamente conocido que existen problemas de decisión en P cuyas versiones de conteo son # P-complete (un ejemplo es 2-SAT). Pero este caso es un poco "diferente" en mi opinión: encontrar una asignación satisfactoria de una instancia Monotone-SAT no solo es fácil (como, por ejemplo, encontrar una asignación satisfactoria de una instancia 2-SAT), es dramáticamente trivial. No solo fácil: trivial, literalmente. Tenga en cuenta que, dada, por ejemplo, una instancia 2-SAT, puede ser satisfactoria o insatisfactoria, por supuesto; Si bien recibe una instancia de Monotone-SAT, sabe de antemano que es ciertamente satisfactoria: no puede ser insatisfactorio, de ninguna manera: esto confirma que, incluso ambos problemas son fáciles, sus niveles de "facilidad para la toma de decisiones" son diferentes. Por otro lado, sus niveles de "conteo-inquietud" son exactamente los mismos.

Este fuerte contraste entre los siguientes hechos

1. Decidir Monotone-SAT es tonto-trivial
2. Contar Monotone-SAT es extremadamente difícil

es en mi humilde opinión al menos fascinante.

Que los axiomas de Elección y Determinación no son compatibles.