Nécrologies de conjectures mortes

Je cherche des hypothèses sur les algorithmes et la complexité qui ont été jugées crédibles par beaucoup à un moment donné, mais qui ont ensuite été réfutées, ou du moins incrédules, en raison de la multiplication des contre-preuves. Voici deux exemples:

1. Hypothèse aléatoire d'oracle: les relations entre les classes de complexité qui sont valables pour presque tous les mondes relativisés sont également valables dans le cas non relativisé. Cela a été réfuté par le résultat et en montrant que est valable pour presque tous les oracles aléatoires , voir L'hypothèse de l'oracle aléatoire est fausse .I P X ≠ P S P A C E X$IP=PSPACE$$IP^X\neq PSPACE^X$$X$

2. Le caractère aléatoire d'erreur bornée étend correctement la puissance du temps polynomial (c'est-à-dire, ). Cela a été cru pendant un certain temps, mais plus tard, en raison de résultats de dérandomisation sophistiqués et de leurs liens avec la complexité du circuit, la conjecture opposée ( ) est devenue répandue (bien que toujours ouverte).P = B P $P\neq BPP$$P=BPP$

Quelles autres conjectures ont échoué à l'épreuve du temps?

N P ≠ c o N $\mathsf{NL} \neq \mathsf{coNL}$ . Avant de parvenir à un résultat égal, je pense que l’on croyait généralement qu’ils étaient distincts, par analogie avec la conviction que (c’est-à-dire le principe général selon lequel "le non-déterminisme et le non-déterminisme est différent "; cela s’est avéré être faux sous des limites de complexité spatiale au moins logarithmiques).$\mathsf{NP} \neq \mathsf{coNP}$

Avant , on pensait que même ne figurait pas dans : dans Fortnow-Sipser 1988, ils avaient supposé que tel était le cas et avaient donné un oracle par rapport auquel il était vrai.C O N P I $\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{coNP}$$\mathsf{IP}$

Les programmes de branchement à largeur constante nécessitent plus que la longueur polynomiale pour compter : après que Furst-Saxe-Sipser et Ajtai aient montré en 1981 que les circuits en CA ⁰ ne pouvaient pas compter, une étape naturelle semblait sembler montrer que les programmes de branchement en largeur constante de polynômes la longueur ne pouvait pas compter, ce qui était largement supposé tenir. David Barrington en 1986 a montré qu’ils pouvaient non seulement compter mais qu’ils étaient équivalents à NC ¹ .

$\mathsf{3SUM}$$\mathsf{3SUM}$$\Omega(n^2)$

$O(n^2/(\log n/\log \log n)^{2/3})$

[1] Triplettes, Dégénérés et Triangles d'Amour. Allan Grønlund et Seth Pettie. Dans Foundations of Computer Science (FOCS) 2014, p. 621-630. arXiv: 1404.0799 [cs.DS]

La solution du dixième problème de Hilbert par Davis, Matiyasevich, Putnam et Robinson, montrant que les ensembles énumérables récursivement sont précisément les ensembles de Diophantine.

(Je reproduis ici un article de blog , Hindsight , paru il y a quelques années, comme suggéré dans les commentaires.)

Extrait de l 'analyse par Georg Kreisel du problème de la décision pour les équations exponentielles de diophantine , par Martin Davis, Hilary Putnam et Julia Robinson, Ann. de maths. (2), 74 (3) , (1961), 425–436. MR0133227 (24 # A3061) .

Cet article établit que chaque (re) ensemble récursivement énumérable peut être défini de manière existentielle par une exponentiation. […] Ces résultats sont superficiellement liés au dixième problème de Hilbert relatif aux équations diophantiennes (ordinaires, c'est-à-dire non exponentielles). La preuve des résultats des auteurs, bien que très élégante, n'utilise pas de faits récursifs ni dans la théorie des nombres ni dans celle des répétitions; il est donc probable que le résultat actuel ne soit pas étroitement lié au dixième problème de Hilbert. De plus, il n'est pas tout à fait plausible que tous les problèmes diophantiens (ordinaires) soient uniformément réductibles à ceux d'un nombre fixe de variables de degré fixe, ce qui serait le cas si tous les cycles étaient diophantiens.

Bien sûr, ma citation préférée concernant le dixième problème va de l'avant-propos de Martin Davis au dixième problème de Yuri Matiyasevich, Hilbert .

Au cours des années 1960, j'ai souvent eu l'occasion de faire une conférence sur le dixième problème de Hilbert. À ce moment-là, on savait que l'insolvabilité découlerait de l'existence d'une équation de Diophantine unique satisfaisant à une condition formulée par Julia Robinson. Cependant, il semblait extrêmement difficile de produire une telle équation et, de fait, l'opinion prédominante était qu'il était peu probable qu'elle en existe. Dans mes conférences, je voudrais souligner les conséquences importantes qui découleraient d'une preuve ou d'une réfutation de l'existence d'une telle équation. Inévitablement, au cours de la période de questions, on me demanderait comment j’allerais les choses, et j’avais ma réponse prête: «Je pense que l’hypothèse de Julia Robinson est vraie et elle sera prouvée par un jeune et intelligent Russe.»

Le programme de Hilbert et sa "conjecture" sur la décidabilité des théories formelles. Il a été formulé au début des années 1920 et a été poursuivi par lui et ses collaborateurs à l’Université de Göttingen et ailleurs dans les années vingt et trente.

"Avec ce nouveau fondement des mathématiques - que l’on peut appeler à juste titre théorie de la preuve -, je crois que nous devons résoudre une fois pour toutes les questions fondamentales des mathématiques en tant que telles, en transformant chaque énoncé mathématique en une formule pouvant être démontrée de manière concrète et rigoureusement, et ensemble complexe de questions dans le domaine des mathématiques pures ".

Il est bien connu que les propositions de Hilbert "se sont écrasées" (assez rapidement [1931]) dans le théorème d'inachèvement de Godel .

Pour un bon aperçu du programme de Hilbert et des développements ultérieurs, voir: Richard Zach; Le programme de Hilbert hier et aujourd'hui; Manuel de philosophie des sciences. Volume 5: Philosophie de la logique; 2006

Voir également la réponse d'Andrés Caicedo à un autre aspect de l'histoire: le dixième problème de Hilbert, qui n'a été résolu qu'en 1970.

$s > 1/2$$\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$

$\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$

(* J'ai trouvé cette conférence de Madhu publiée dans "Computational Complexity Theory" de Rudich / Wigderson ")

les conjectures vont du formel à l'informel. Par exemple, la fameuse conjecture de Hilberts sur la décidabilité des mathématiques a été formalisée en quelques problèmes, par exemple le 10ème problème de Hilberts, mais il s'agissait également d'une conjecture informelle plus grandiose couvrant l'ensemble du domaine. cela peut aussi être vu comme un programme de recherche proposé.

Une recette facile pour trouver une telle "notice nécrologique de conjectures mortes" serait de considérer la "méta" déclaration "[x] la conjecture pourrait être prouvée de mon vivant." La littérature mathématique est pleine de telles déclarations / attentes qui se sont révélées être "fausses" dans le sens de défier complètement les attentes concernant la difficulté et l'accessibilité d'une preuve. La conjecture de Riemann, classique depuis plus d'un siècle et demi, en est un classique. L’application de ce même modèle à la théorie de la complexité n’est pas aussi simple, car la théorie de la complexité est un domaine scientifique beaucoup plus jeune. cependant, voici un exemple clé.

la découverte précoce du problème P vs NP (maintenant ouverte depuis quatre décennies et demi) avait une sorte d'innocence en ce que les enquêteurs d'origine ne pouvaient pas et n'auraient pas pu imaginer à quel point le problème allait devenir difficile ou transversal. Pour rendre cela plus spécifique, considérons le domaine de la complexité des circuits inventé au début des années 1980, par exemple par Sipser. Il s’agissait d’un programme de recherche un peu semblable à celui que Hilberts avait mis en place pour attaquer P vs NP. Arvind résume une partie du résultat historique dans ce résumé / introduction. La colonne de complexité des calculs, BEATCS 106 :

Les années 1980 étaient une période en or pour les limites inférieures de la complexité du circuit booléen. Il y a eu des avancées majeures. Par exemple, la limite inférieure de taille exponentielle de Razborov pour les circuits booléens monotones calculant la fonction Clique et les limites inférieures de taille superpolynomiale de Razborov-Smolensky pour les circuits à profondeur constante avec des portes MOD _p pour prime p. Ces résultats ont rendu les chercheurs optimistes quant aux progrès réalisés sur les grandes questions de la limite inférieure et les séparations de classes de complexité. Cependant, au cours des deux dernières décennies, cet optimisme s'est progressivement transformé en désespoir. Nous ne savons toujours pas comment prouver les bornes inférieures superpolynomiales pour des circuits à profondeur constante avec des portes MOD ₆ pour une fonction calculable en temps exponentiel.

Deux documents clés ont anéanti tout espoir sur le terrain. Razborov a obtenu d'excellents résultats sur la fonction Clique, mais a ensuite écrit deux articles opposés. un article a montré que l'appariement, un problème de temps de calcul, nécessite des circuits monotones exponentiels et que, dans un certain sens, l'approche des circuits monotones vers les bornes inférieures a été contrecarrée en raison d'un manque de correspondance dans la complexité des circuits non monotones ("complets") compris).

ceci a été développé dans son article Natural Natural Proofs, en collaboration avec Rudich, dans lequel il est montré que toutes les preuves de limite inférieure de circuit antérieures sont soumises à un modèle particulier qui présente une faiblesse démontrable au sens de la contradiction avec les limites inférieures conjecturées sur les générateurs de nombres aléatoires durs de cryptographie.

ainsi, dans une certaine mesure, les circuits sont "tombés en panne". Il s'agit toujours d'un vaste domaine de recherche, mais la sagesse conventionnelle, étayée par les résultats techniques, est qu'une sorte de structure / structure de preuves encore inconnue serait nécessaire pour obtenir des résultats probants dans la région, si possible. En fait, de la même façon, on pourrait penser que, même dans l’ensemble, les «limites inférieures fortes de la théorie de la complexité» sont considérées comme extrêmement difficiles et que cela n’était pas largement prévu ou prévu dans les tout premiers jours du terrain. mais d'autre part, cela les classe ensuite en difficulté / signification / importance avec les gros problèmes (ouverts) des mathématiques.