Resultados surpreendentes em complexidade (não está na lista de blogs de complexidade)

Quais foram os resultados mais surpreendentes em complexidade?

Eu acho que seria útil ter uma lista de resultados inesperados / surpreendentes. Isso inclui resultados surpreendentes e surgidos do nada, além de resultados diferentes do que as pessoas esperavam.

Edit : dada a lista de Gasarch, Lewis e Ladner no blog de complexidade (apontado por @Zeyu), vamos focar este wiki da comunidade nos resultados que não estão em sua lista. Talvez isso leve a um foco nos resultados após 2005 (conforme sugestão de @ Jukka).

Um exemplo: Aprendizado fraco = aprendizado forte [Schapire 1990] : (Surpreendentemente?) Ter alguma vantagem sobre adivinhações aleatórias faz com que você aprenda o PAC. Levar ao algoritmo AdaBoost.

Aqui está o post de convidado de Bill Gasarch, com a ajuda de Harry Lewis e Richard Ladner: http://blog.computationalcomplexity.org/2005/12/surprising-results.html

Se , existe uma prova de "diagonalização" para isso.$P \neq NP$

Este resultado é devido a Kozen. Nem todo mundo concorda com o que ele chama de prova de "diagonalização".

Na Barreiras I, um painel dos principais teóricos da complexidade concordou que o Teorema de Barrington foi o resultado que mais os surpreendeu. Fortnow explica o teorema de Barrington aqui: http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html

$NL$

Eu diria que o trabalho recente de Jain, Upadhyay e Watrous mostrando que QIP = IP = PSPACE é bastante surpreendente. Minha opinião é que não é tão interessante que QIP = IP seja interessante, mas sim o fato de que todo o QIP pode ser simulado em uma prova interativa quântica de três etapas. Uma demonstração bastante interessante do poder do paralelismo quântico.

Algo que continua a me surpreender é que o BPP provavelmente será P - Isso traz muitas questões filosóficas sobre a natureza da aleatoriedade.

Teoremas da incompletude de Gödel

Teorema de Razborov-Rudich Natural Proofs.

(AFAIK) As pessoas estavam muito esperançosas em provar limites mais baixos do circuito, mas após esse teorema muitos pararam de trabalhar e passaram para outros tópicos.

A versão de contagem do problema Monotone-SAT é # P-complete.

$F$$F$

Fiquei muito surpreso com esse resultado, porque a versão de decisão do problema Monotone-SAT é trivial.

É sabido que existem problemas de decisão em P cujas versões de contagem são # P-completas (um exemplo é 2-SAT). Mas esse caso é um pouco "diferente" na minha opinião: encontrar uma atribuição satisfatória de uma instância Monotone-SAT não é apenas fácil (como, por exemplo, encontrar uma atribuição satisfatória de uma instância 2-SAT), é dramaticamente trivial. Não é fácil: trivial, literalmente. Observe que, dada, por exemplo, uma instância 2-SAT, ela pode ser satisfatória ou insatisfatória, é claro; embora, dada uma instância do Monotone-SAT, você saiba com antecedência que ela certamente é satisfatória: não pode ser insatisfatória, de jeito nenhum: isso confirma que, mesmo os dois problemas são fáceis, seus níveis de "facilidade de decisão" são diferentes. Por outro lado, seus níveis de "desconforto-contagem" são exatamente os mesmos.

Esse forte contraste entre os seguintes fatos

1. Decidir Monotone-SAT é burro-trivial
2. Contar Monotone-SAT é extremamente difícil

é IMHO pelo menos fascinante.

Que os axiomas da escolha e da determinação não são compatíveis.