Obituarios de conjeturas muertas

44

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=PSPACEIPXPSPACEXX

  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).PBPPP=BPP

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

Andras Farago
fuente
3
Antes de IP = PSPACE, incluso se creía posible que , ver Fortnow-Sipser 1988 . No sé si esto cuenta como una respuesta separada con la misma resolución, o si es demasiado similar a su ejemplo 1.coNPIP
Joshua Grochow
44
El programa de Hilbert ("... deshacerse de las preguntas fundamentales en matemáticas como tales de una vez por todas ...") y su "conjetura" sobre la capacidad de decisión de las teorías formales [~ 1920], que "se estrelló" (bastante rápido [1931 ]) en el teorema de incompletitud de Godel :-)
Marzio De Biasi
2
La revisión de este artículo, por Kreisel, dice "Este artículo establece que cada (re) conjunto recursivamente enumerable puede definirse existencialmente en términos de exponenciación ... Estos resultados están superficialmente relacionados con el décimo problema de Hilbert en (ordinario, es decir, no exponencial ) Ecuaciones de diofantina ... 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 restablecimientos fueran diofantina ". (Ver también aquí .)
Andrés E. Caicedo
3
También la publicación Resultados Sorprendentes del blog de Complejidad Computacional.
Kaveh

Respuestas:

22

NLcoNL . 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).NPcoNP

Joshua Grochow
fuente
'analogía'? uno es tiempo y otro es espacio no?
77
@Arul: Sí. Esa es una analogía entre las clases de complejidad definidas por el tiempo límite y las clases de complejidad definidas por el espacio límite ...
Joshua Grochow
Pero el tiempo y el espacio no son equivalentes (al menos conjetural)
25
@Arul: Correcto. Es precisamente por eso que es solo una analogía ...
Joshua Grochow
19

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.IP=PSPACEcoNPIP

Joshua Grochow
fuente
18

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 0 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 1 .

Paul Beame
fuente
17

La : que cualquier algoritmo determinista para requiere tiempo .3SUM3SUMΩ(n2)

Esto fue refutado en 2014 por Allan Grønlund y Seth Pettie, quienes dieron un algoritmo determinista que se ejecuta en tiempo [1].O(n2/(logn/loglogn)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]

Mangara
fuente
55
¿Cómo demonios consiguieron ese título más allá de los críticos?
David Zhang
17

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".

Andrés E. Caicedo
fuente
9

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.

Marzio De Biasi
fuente
7

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/2PCP1,s[logn,3]P

De hecho, SDP muestra , lo que da un estrecho límite a la complejidad de dichos PCP.PCP1,1/2[logn,3]=P

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

Joe Bebel
fuente
1

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 6 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.

vzn
fuente
1
¿Qué conjetura estás resaltando? Además, la complejidad del circuito parece ser muy activa y bastante exitosa, por ejemplo, los múltiples avances de Rossman; vea el libro de texto autorizado de Jukna para obtener una descripción más sólida del campo.
András Salamon
existen múltiples ideas interrelacionadas, pero, por ejemplo, la conjetura "aproximada" de que los circuitos en general o alguna forma especial (por ejemplo, monótona) podrían probar P vs NP o límites inferiores fuertes ... nunca se formalizó exactamente pero circula en muchos (antiguos) documentos de teoría de circuitos. tampoco está estrictamente refutado, pero se revisó en gran medida con la retrospectiva de 2020. La historia del circuito monótono en particular es una "casi reversión".
vzn
8
Si citó algunas referencias específicas como soporte para un circuito monótono, entonces esa sería una buena respuesta. Pero lo anterior parece arrojar muchas palabras a la pared y esperar un poco; Tiene matices pero carece de una tesis clara. En mi lectura, no me he dado la impresión de que los circuitos monótonos hayan sido considerados especialmente poderosos.
András Salamon
@ AndrásSalamon: Creo que esa vista representa el beneficio de la retrospectiva. Es decir, después del límite inferior exponencial de Razborov en los circuitos monótonos para la camarilla, creo que hubo un optimismo bastante generalizado de que los límites inferiores del circuito mucho más grandes (como ) estaban "a la vuelta de la esquina". (Tal vez no tan extendido como la creencia de que , pero creo que lo suficientemente extendido como para que valga la pena mencionarlo como respuesta a esta pregunta).NPP/polyPneqNP
Joshua Grochow
@JoshuaGrochow, estoy de acuerdo, pero eso es bastante diferente del hilo enredado anterior. ¿Quizás valga la pena publicarlo como respuesta?
András Salamon