Obituarios de conjeturas muertas

Estoy buscando conjeturas sobre algoritmos y complejidad que muchos consideraron creíbles en algún momento, pero que luego fueron refutadas, o al menos no creídas, debido a la creciente evidencia contraria. Aquí hay dos ejemplos:

1. Hipótesis de oráculo aleatorio: las relaciones entre clases de complejidad que se mantienen para casi todos los mundos relativizados, también se mantienen en el caso no relativizado. Esto fue refutado por el resultado , y al mostrar que es válido para casi todos los oráculos aleatorios , ver La hipótesis del oráculo aleatorio es falsa .$IP=PSPACE$$IP^X\neq PSPACE^X$$X$

2. La aleatoriedad del error acotado extiende adecuadamente la potencia del tiempo polinómico (es decir, ). Esto se creyó durante un tiempo, pero más tarde, debido a los sofisticados resultados de desrandomización y sus conexiones con la complejidad del circuito, la conjetura opuesta ( ) se ha vuelto prevalente (aunque todavía abierta).$P\neq BPP$$P=BPP$

¿Cuáles son algunas otras conjeturas que no pasaron la prueba del tiempo?

$\mathsf{NL} \neq \mathsf{coNL}$ . Antes del resultado de que estos dos eran iguales, creo que se creía ampliamente que eran distintos, por analogía con la creencia de que (es decir, el principio general de que "no determinismo y co- el no determinismo es diferente "; esto resultó ser falso bajo los límites de complejidad espacial que eran al menos logarítmicos).$\mathsf{NP} \neq \mathsf{coNP}$

Antes de , se creía posible que incluso no estuviera contenido en : en Fortnow-Sipser 1988 conjeturaron que ese era el caso y dieron un oráculo con respecto al cual era cierto.$\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{coNP}$$\mathsf{IP}$

Los programas de ramificación de ancho constante requieren más que la longitud del polinomio para contar : después de que Furst-Saxe-Sipser y Ajtai en 1981 mostraron que los circuitos AC ⁰ no pueden contar, un siguiente paso natural parecía ser mostrar que los programas de ramificación de polinomio de ancho constante la longitud no podía contar, lo que se conjeturó ampliamente que aguantaba. David Barrington en 1986 demostró que no solo pueden contar, sino que son equivalentes a NC ¹ .

La : que cualquier algoritmo determinista para requiere tiempo .$\mathsf{3SUM}$$\mathsf{3SUM}$$\Omega(n^2)$

Esto fue refutado en 2014 por Allan Grønlund y Seth Pettie, quienes dieron un algoritmo determinista que se ejecuta en tiempo [1].$O(n^2/(\log n/\log \log n)^{2/3})$

[1] Tríos, degenerados y triángulos amorosos. Allan Grønlund y Seth Pettie. En Fundamentos de Informática (FOCS) 2014, pp. 621-630. arXiv: 1404.0799 [cs.DS]

La solución del décimo problema de Hilbert por Davis, Matiyasevich, Putnam y Robinson, que muestra que los conjuntos recursivamente enumerables son precisamente los conjuntos de Diophantine.

(Estoy reproduciendo aquí una publicación de blog , Hindsight , de hace un par de años, como se sugiere en los comentarios).

De la revisión de Georg Kreisel de El problema de decisión para ecuaciones exponenciales de diofantina , por Martin Davis, Hilary Putnam y Julia Robinson, Ann. de matemáticas (2), 74 (3) , (1961), 425–436. MR0133227 (24 # A3061) .

Este artículo establece que cada (re) conjunto recursivamente enumerable puede definirse existencialmente en términos de exponenciación. [...] Estos resultados están relacionados superficialmente con el décimo problema de Hilbert en ecuaciones de diofantina (ordinarias, es decir, no exponenciales). La prueba de los resultados de los autores, aunque muy elegante, no utiliza hechos recónditos en la teoría de números ni en la teoría de los reinicios, por lo que es probable que el resultado actual no esté estrechamente relacionado con el décimo problema de Hilbert. Además, no es del todo posible que todos los problemas de diofantina (ordinarios) sean uniformemente reducibles a aquellos en un número fijo de variables de grado fijo, que sería el caso si todos los reinicios fueran diofantina.

Por supuesto, mi cita favorita en relación con el décimo problema es del Prólogo de Martin Davis al décimo problema de Hilbert de Yuri Matiyasevich .

Durante la década de 1960 a menudo tuve la oportunidad de dar una conferencia sobre el Décimo problema de Hilbert. En ese momento se sabía que la indisolución se derivaría de la existencia de una sola ecuación de diofantina que satisficiera una condición formulada por Julia Robinson. Sin embargo, parecía extraordinariamente difícil producir tal ecuación, y de hecho, la opinión predominante era que era poco probable que existiera. En mis conferencias, enfatizaría las importantes consecuencias que se derivarían de una prueba o una prueba de la existencia de tal ecuación. Inevitablemente, durante el período de preguntas, me pedirían mi propia opinión sobre cómo saldrían las cosas, y tenía lista mi respuesta: "Creo que la hipótesis de Julia Robinson es cierta, y será probada por un joven ruso inteligente".

El programa de Hilbert y su "conjetura" sobre la capacidad de decisión de las teorías formales. Fue formulado a principios de la década de 1920 y fue perseguido por él y sus colaboradores en la Universidad de Gottingen y en otros lugares en las décadas de 1920 y 1930.

"Con esta nueva base de las matemáticas, que se puede llamar apropiadamente una teoría de prueba, creo que es necesario deshacerse de las preguntas fundamentales de las matemáticas como tal de una vez por todas al convertir cada enunciado matemático en una fórmula concretamente exhibible y rigurosamente derivable y, por lo tanto, transferir la todo un complejo de preguntas en el dominio de las matemáticas puras ".

Es bien sabido que las propuestas de Hilbert "chocaron" (bastante rápido [1931]) en el teorema de incompletitud de Godel .

Para una buena visión general del programa de Hilbert y desarrollos posteriores, ver: Richard Zach; El programa de Hilbert entonces y ahora; Manual de la filosofía de la ciencia. Volumen 5: Filosofía de la lógica; 2006

Vea también la respuesta de Andrés Caicedo para otro aspecto de la historia: el décimo problema de Hilbert que se resolvió solo en 1970.

En una conferencia de Madhu Sudán *, afirmó que existía cierta creencia de que existe modo que , a través de programación semidefinida, antes de la prueba del teorema PCP de tres bits de Håstad.$s > 1/2$$\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$

De hecho, SDP muestra , lo que da un estrecho límite a la complejidad de dichos PCP.$\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$

(* Encontré esta conferencia de Madhu publicada en "Teoría de la complejidad computacional editada por Rudich / Wigderson")

las conjeturas varían en un espectro de formal a informal. por ejemplo, la famosa conjetura de Hilbert sobre la capacidad de decisión de las matemáticas se formalizó en algunos problemas, por ejemplo, el décimo problema de Hilbert, pero también fue una conjetura informal más grandiosa que abarca todo el campo. También puede verse como un programa de investigación propuesto.

una receta fácil para encontrar tal "obituario de conjeturas muertas" sería considerar la "conjetura de" meta "" declaración "[x] que podría probarse en mi vida". La literatura matemática está llena de declaraciones / expectativas que resultaron ser "falsas" en el sentido de desafiar completamente las expectativas sobre la dificultad y la accesibilidad de una prueba. una clásica es la conjetura de Riemann, abierta por más de ~ 1½ siglo. aplicar este mismo modelo a la teoría de la complejidad no es tan fácil porque la teoría de la complejidad es un campo científico mucho más joven. Sin embargo, aquí hay un ejemplo clave.

El descubrimiento temprano del problema P vs NP (ahora abierto 4½ décadas) tuvo una especie de inocencia en el sentido de que los investigadores originales no tenían ni podían haber imaginado cuán difícil o transversal sería el problema. Para hacer esto más específico, considere el campo de la complejidad del circuito inventado a principios de la década de 1980, por ejemplo, por Sipser. Este fue un programa de investigación similar a Hilberts montado en parte para atacar P vs NP. Arvind resume algunos de los resultados históricos en este resumen / introducción La columna de complejidad computacional, BEATCS 106 :

La década de 1980 fue un período dorado para los límites inferiores de la complejidad del circuito booleano. Hubo avances importantes. Por ejemplo, el límite inferior del tamaño exponencial de Razborov para circuitos booleanos monótonos que calculan la función Clique y los límites inferiores del tamaño superpolinómico de Razborov-Smolensky para circuitos de profundidad constante con compuertas MOD _p para p primo. Estos resultados hicieron a los investigadores optimistas sobre el progreso en grandes preguntas de límite inferior y separaciones de clase de complejidad. Sin embargo, en las últimas dos décadas, este optimismo se convirtió gradualmente en desesperación. Todavía no sabemos cómo probar los límites inferiores superpolinomiales para circuitos de profundidad constante con compuertas MOD ₆ para una función computable en tiempo exponencial.

Hubo dos documentos clave que derribaron las esperanzas en el campo. Razborov tuvo excelentes resultados en la función Clique, pero luego escribió dos artículos opuestos. un artículo mostró que Matching, un problema de tiempo P, requiere circuitos monótonos exponenciales y, por lo tanto, en cierto sentido, el enfoque del circuito monótono hacia los límites inferiores se vio frustrado debido a la falta de correspondencia en la complejidad con los circuitos no monótonos ("completos") (todavía no completamente entendido).

esto se amplió en su famoso artículo Natural Proofs, en coautoría con Rudich, en el que se muestra que todas las pruebas de límites inferiores de circuitos anteriores están sujetas a un patrón particular que tiene debilidad demostrable en el sentido de entrar en conflicto con límites inferiores conjeturados en generadores de números aleatorios duros de criptografía.

entonces, hasta cierto punto, los circuitos han "caído en desgracia". Todavía es un área de investigación masiva, pero la sabiduría convencional, respaldada por resultados técnicos, es que se requeriría algún tipo de patrón / estructura de prueba especial aún desconocida para obtener resultados sólidos en el área, si es realmente posible. de hecho, de manera similar, uno podría sugerir que incluso los "límites inferiores fuertes en la teoría de la complejidad" en general ahora se consideran extremadamente difíciles, y esto no era ampliamente esperado / predicho en los días más jóvenes del campo. pero, por otro lado, esto los clasifica allí en dificultad / importancia / importancia con los grandes problemas (abiertos) de las matemáticas.