A Hipótese do Tempo Exponencial é Falsa [pdf]
Um novo preprint da OpenAI afirma refutar a Hipótese do Tempo Exponencial ao apresentar um algoritmo em tempo subexponencial para 3-SAT, um problema NP-completo emblemático. Os comentaristas destacam que isso é um grande avanço teórico que derruba uma hipótese de dureza amplamente usada e enfraquece um pouco a confiança na crença de que P≠NP, embora ainda fique muito aquém de uma solução prática ou em tempo polinomial e deixe a maioria dos problemas em NP potencialmente exponenciais. Grande parte da conversa gira em torno do que esse limite de tempo realmente implica, por que ele não torna automaticamente todos os problemas em NP subexponenciais nem quebra a criptografia, e como algoritmos “galácticos” como este ainda assim podem mudar intuições sobre que tipos de algoritmos são possíveis.
Significado e relação com P vs NP
- Muitos comentaristas veem isto como um enorme resultado teórico, “na mesma liga” que P vs NP, mas enfatizam que ele não resolve P vs NP.
- O fato de ETH ser falsa remove uma hipótese amplamente usada; muito trabalho anterior que dependia de ETH/SETH pode precisar ser revisitado.
- Alguns interpretam isso como uma redução da confiança em P≠NP; outros argumentam que isso realmente não muda muita coisa, exceto mostrar que nossas intuições sobre problemas “difíceis” estavam equivocadas.
O que o resultado realmente afirma
- ETH dizia que k‑SAT (tipicamente 3‑SAT) requer tempo ~2^{Ω(n)}.
- O artigo apresenta um algoritmo subexponencial, aproximadamente 2^{n / √log n}, então ETH é falsa.
- A discussão corrige repetidamente um equívoco: isto não prova NP≠EXP ou NP⊊EXP.
Reduções e por que NP não foi provado subexponencial
- Nuance importante: problemas em NP se reduzem a SAT em tempo polinomial, mas reduções polinomiais podem aumentar o tamanho da instância.
- Limites da forma 2^{o(n)} não se propagam automaticamente por reduções polinomiais arbitrárias; seria necessário 2^{n^{o(1)}}.
- Portanto, 3‑SAT ser subexponencial não implica que todos os সমস্যas em NP sejam subexponenciais.
- Isso de fato se transfere para problemas linearmente redutíveis a SAT (por exemplo, certos problemas de contagem listados no artigo).
Tentativas de explicação simples e intuição de complexidade
- Vários comentários oferecem explicações leigas de SAT, NP e ETH, enfatizando:
- NP = eficientemente verificável (com uma dica), não necessariamente eficientemente solucionável.
- Subexponencial ainda pode ser astronomicamente grande; há um abismo enorme entre tempo polinomial e exponencial.
Impacto prático e algoritmos “galácticos”
- Especialistas em solucionadores de SAT chamam os algoritmos de “galácticos”: as constantes são tão grandes que instâncias do mundo real continuam melhor atendidas pelos solucionadores existentes.
- Instâncias reais de SAT costumam ser muito mais fáceis que o pior caso; não se esperam ganhos imediatos de desempenho.
Implicações mais amplas e reações
- Alguns veem isso como um pequeno deslocamento da intuição em direção a “talvez existam algoritmos engenhosos que ainda não imaginamos”, alinhando-se com visões mais antigas de que muitos problemas poderiam admitir algoritmos mais rápidos.
- Outros se preocupam com se “eficiente” em teoria da complexidade coincide com noções do mundo real, sugerindo que P vs NP pode ser um proxy mal formulado para eficiência prática.
- Há curiosidade e especulação sobre impactos na criptografia, mas a discussão observa que nenhum criptossistema atual é obviamente quebrado por esse resultado.