Obituários de conjecturas mortas

Estou procurando conjecturas sobre algoritmos e complexidade que foram vistas por muitos em algum momento credíveis, mas mais tarde elas foram refutadas ou, pelo menos, desacreditadas, devido à crescente contra-evidência. Aqui estão dois exemplos:

1. Hipótese aleatória do oráculo: relações entre classes de complexidade que são válidas para quase todos os mundos relativizados, também são válidas no caso não relativizado. Isso foi refutado pelo resultado e, ao mostrar que é válido para quase todos os oráculos aleatórios , consulte A hipótese aleatória do Oracle é falsa .I P X ≠ P S P A C E X$IP=PSPACE$$IP^X\neq PSPACE^X$$X$

2. A aleatoriedade do erro limitado estende adequadamente o poder do tempo polinomial (isto é, ). Isso foi acreditado por um tempo, mas mais tarde, devido aos sofisticados resultados de des aleatorização e suas conexões com a complexidade do circuito, a conjectura oposta ( ) tornou-se predominante (embora ainda esteja aberta).P = B P $P\neq BPP$$P=BPP$

Quais são algumas outras conjecturas que falharam no teste do tempo?

$\mathsf{NL} \neq \mathsf{coNL}$ . Antes do resultado de que esses dois eram iguais, eu acreditava-se amplamente que eles eram distintos, por analogia com a crença de que (isto é, o princípio geral de que "não-determinismo e co- o não determinismo é diferente "; isso se mostrou falso sob limites de complexidade espacial que eram pelo menos logarítmicos).$\mathsf{NP} \neq \mathsf{coNP}$

Antes de , pensava-se possível que mesmo não estivesse contido em : em Fortnow-Sipser 1988 eles conjeturaram que esse era o caso e deram um oráculo em relação ao qual era verdade.$\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{coNP}$$\mathsf{IP}$

Os programas de ramificação de largura constante requerem mais do que o comprimento polinomial para serem contados : depois que Furst-Saxe-Sipser e Ajtai, em 1981, mostraram que os circuitos AC ⁰ não podem contar, um próximo passo natural parecia ser mostrar que os programas de ramificação de largura constante de polinômios o comprimento não podia contar, o que era amplamente conjeturado. David Barrington, em 1986, mostrou que eles não apenas podem contar, mas também são equivalentes ao NC ¹ .

A : que qualquer algoritmo determinístico para requer tempo .$\mathsf{3SUM}$$\mathsf{3SUM}$$\Omega(n^2)$

Isso foi refutado em 2014 por Allan Grønlund e Seth Pettie, que forneceram um algoritmo determinístico que é executado no tempo [1].$O(n^2/(\log n/\log \log n)^{2/3})$

[1] Ménage à Trois, degenerados e triângulos amorosos. Allan Grønlund e Seth Pettie. In Foundations of Computer Science (FOCS) 2014, pp. 621-630. arXiv: 1404.0799 [cs.DS]

A solução do décimo problema de Hilbert por Davis, Matiyasevich, Putnam e Robinson, mostrando que os conjuntos recursivamente enumeráveis ​​são precisamente os conjuntos diofantinos.

(Estou reproduzindo aqui uma postagem no blog , Hindsight , de alguns anos atrás, conforme sugerido nos comentários.)

Da revisão de Georg Kreisel sobre O problema da decisão para equações diofantinas exponenciais , por Martin Davis, Hilary Putnam e Julia Robinson, Ann. de matemática. (2), 74 (3) , (1961), 425-436. MR0133227 (24 # A3061) .

Este artigo estabelece que todo (re) conjunto recursivamente enumerável pode ser definido existencialmente em termos de exponenciação. […] Esses resultados estão superficialmente relacionados ao décimo problema de Hilbert nas equações diofantinas (comuns, isto é, não exponenciais). A prova dos resultados dos autores, embora muito elegante, não usa fatos recônditos na teoria dos números nem na teoria dos rearranjos, e, portanto, é provável que o resultado presente não esteja intimamente ligado ao décimo problema de Hilbert. Também não é totalmente plausível que todos os problemas diofantinos (comuns) sejam redutíveis de maneira uniforme para aqueles em um número fixo de variáveis ​​de grau fixo, o que seria o caso se todos os reinícios fossem diofantinos.

Naturalmente, minha citação favorita em relação ao décimo problema é do Prefácio de Martin Davis ao décimo problema de Hilbert, de Yuri Matiyasevich .

Nos anos 60, tive a oportunidade de dar uma palestra sobre o Décimo Problema de Hilbert. Naquela época, sabia-se que a insolubilidade decorreria da existência de uma única equação diofantina que satisfizesse uma condição formulada por Julia Robinson. No entanto, parecia extraordinariamente difícil produzir essa equação e, de fato, a opinião predominante era que era improvável que existisse. Nas minhas palestras, enfatizaria as importantes consequências que se seguiriam de uma prova ou de uma refutação da existência de uma equação desse tipo. Inevitavelmente, durante o período de perguntas, perguntaram-me a minha opinião sobre como as coisas terminariam e eu já tinha a minha resposta: "Penso que a hipótese de Julia Robinson é verdadeira e será provada por um jovem russo inteligente".

O programa de Hilbert e sua "conjectura" sobre a decidibilidade das teorias formais. Foi formulado no início dos anos 1920 e foi perseguido por ele e seus colaboradores na Universidade de Göttingen e em outros lugares nas décadas de 1920 e 1930.

"Com esse novo fundamento da matemática - que se pode chamar apropriadamente de teoria da prova - acredito que descartar as questões fundamentais da matemática como tal de uma vez por todas, transformando cada afirmação matemática em uma fórmula concretamente exibível e rigorosamente derivável e, assim, transferindo a todo complexo de questões no domínio da matemática pura ".

É sabido que as propostas de Hilbert "colidiram" (muito rapidamente [1931]) com o teorema da incompletude de Godel .

Para uma boa visão geral do programa de Hilbert e desenvolvimentos posteriores, consulte: Richard Zach; Programa de Hilbert, então e agora; Manual da filosofia da ciência. Volume 5: Filosofia da Lógica; 2006

Veja também a resposta de Andrés Caicedo para outro aspecto da história: o décimo problema de Hilbert que foi resolvido apenas em 1970.

Em uma palestra de Madhu Sudan *, ele afirmou que havia alguma crença de que existem tais que , via programação semidefinida, antes da prova do teorema PCP de três bits de Håstad.$s > 1/2$$\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$

De fato, o SDP mostra , fornecendo uma forte ligação à complexidade de tais PCPs.$\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$

(* Encontrei esta palestra de Madhu publicada em "Teoria da Complexidade Computacional editada por Rudich / Wigderson")

as conjecturas variam de formal a informal. por exemplo, a famosa conjectura de Hilberts sobre a decidibilidade da matemática foi formalizada em alguns problemas, por exemplo, o 10º problema de Hilberts, mas também era uma conjectura informal mais grandiosa, abrangendo todo o campo. também pode ser visto como um programa de pesquisa proposto.

uma receita fácil para encontrar esse "obituário de conjecturas mortas" seria considerar que a "meta-" afirmação "[x] conjectura poderia ser provada em minha vida". a literatura matemática está cheia de afirmações / expectativas que se revelaram "falsas" no sentido de desafiar totalmente as expectativas sobre dificuldade e acessibilidade de uma prova. uma clássica é a conjectura de Riemann, aberta por mais de meio século. aplicar esse mesmo modelo à teoria da complexidade não é tão fácil porque a teoria da complexidade é um campo científico muito mais jovem. no entanto, aqui está um exemplo importante.

a descoberta precoce do problema P vs NP (agora aberta 4 ½ décadas) teve uma espécie de inocência, pois os investigadores originais não tinham e não poderiam ter imaginado o quão difícil ou transversal seria o problema. para tornar isso mais específico, considere o campo da complexidade do circuito inventado no início dos anos 80, por exemplo, pela Sipser. este foi um programa de pesquisa semelhante ao Hilberts montado em parte para atacar P vs NP. parte do resultado histórico é resumida por Arvind neste resumo / introdução The computational Complexity Column, BEATCS 106 :

A década de 1980 foi um período de ouro para os limites inferiores da complexidade do circuito booleano. Houve grandes avanços. Por exemplo, o tamanho exponencial do Razborov limite inferior para monótonas circuitos booleanos de computação a função Click e o tamanho superpolynomial Razborov-Smolensky limites inferiores para circuitos de profundidade constante com MOD _p portões para primo p. Esses resultados tornaram os pesquisadores otimistas do progresso em grandes questões de limite inferior e separações de classes de complexidade. No entanto, nas últimas duas décadas, esse otimismo gradualmente se transformou em desespero. Ainda não sabemos como provar limites inferiores superpolinomiais para circuitos de profundidade constante com portas MOD ₆ para uma função computável em tempo exponencial.

havia dois documentos importantes que derrubaram as esperanças no campo. Razborov teve ótimos / celebrados resultados na função Clique, mas depois escreveu dois trabalhos opostos. um artigo mostrou que a correspondência, um problema no tempo P, requer circuitos monótonos exponenciais e, portanto, em certo sentido, a abordagem do circuito monótono para limites inferiores foi frustrada devido à falta de correspondência na complexidade com circuitos não monotônicos ("completos") (ainda não totalmente Entendido).

isso foi expandido em seu famoso artigo Natural Proofs, em co-autoria com Rudich, no qual é demonstrado que todas as provas de limites inferiores de circuitos anteriores estão sujeitas a um padrão particular que possui uma fraqueza comprovável no sentido de conflitar com limites inferiores conjecturados em geradores de números aleatórios difíceis de criptografia.

assim, até certo ponto, os circuitos "caíram da graça". ainda é uma área de pesquisa massiva, mas a sabedoria convencional, apoiada em resultados técnicos, é que algum tipo de estrutura / padrão de prova especial ainda desconhecida seria necessária para obter resultados fortes na área, se possível. de fato, da mesma forma, pode-se sugerir que mesmo "limites mais baixos fortes na teoria da complexidade" agora são vistos como extremamente difíceis, e isso não era amplamente esperado / previsto nos dias mais jovens do campo. mas, por outro lado, isso os classifica em dificuldade / importância / importância com os grandes problemas (abertos) da matemática.