Hipótese do tempo exponencial (ETH)

Alguns problemas nós só sabemos resolver testando quase todas as possibilidades. A hipótese do tempo exponencial, em inglês Exponential Time Hypothesis e abreviada como ETH, é a aposta dos cientistas da computação de que, para um problema específico, não vai dar para fazer de outro jeito, por mais espertos que sejamos. Existem métodos mais rápidos, mas até os melhores vão precisar de um número de passos que cresce exponencialmente com o tamanho do problema.

A ETH está intimamente ligada ao problema P versus NP, sobre o qual temos um artigo separado. Se você ainda não o leu, dê uma olhada lá primeiro, porque vamos partir dele. Principalmente do que é a complexidade de um algoritmo e de por que existe um abismo tão grande entre n² e 2ⁿ.

Quem convidar para a festa

Você está organizando uma festa e quer convidar quatro amigos: Thiago, João, Karina e Daniel. O problema é que entre eles há relações de todo tipo, e você gostaria que todos ficassem satisfeitos. Depois de muito perguntar, você chega a seis condições:

1. Vem o Thiago ou a Karina (ou os dois).
2. O João e a Karina não se suportam, então não vêm os dois.
3. O Daniel só vem se o João também vier.
4. Se o Thiago vier, a Karina ou o Daniel também precisa vir.
5. Se o Thiago e a Karina vierem, o João também precisa vir.
6. Vem pelo menos um dos três: Thiago, João, Daniel.

Quem convidar para que todas as condições valham ao mesmo tempo? Tente descobrir sozinho; a solução está escondida no fim do artigo.

Um cientista da computação reescreveria o problema na linguagem da lógica proposicional. Cada amigo ganha uma letra, por exemplo T de Thiago. A letra é verdadeira (o Thiago vem) ou falsa (o Thiago não vem). O símbolo ∨ se lê “ou” e ¬ se lê “não”. A primeira condição fica assim:

$$T\vee K$$

A segunda condição diz que o João não vem ou a Karina não vem:

$$\mathrm{\neg }J\vee \mathrm{\neg }K$$

Na terceira condição é fácil se confundir. “O Daniel só vem se o João também vier” significa que não pode acontecer de o Daniel vir e o João não. Ou seja, ou o Daniel não vem, ou o João vem:

$$\mathrm{\neg }D\vee J$$

Do mesmo jeito reescrevemos o resto. O problema inteiro fica assim:

$$\begin{array}{rcl}1.& & T\vee K\\ 2.& & \mathrm{\neg }J\vee \mathrm{\neg }K\\ 3.& & \mathrm{\neg }D\vee J\\ 4.& & \mathrm{\neg }T\vee K\vee D\\ 5.& & \mathrm{\neg }T\vee \mathrm{\neg }K\vee J\\ 6.& & T\vee J\vee D\end{array}$$

Veja como as condições são parecidas: algumas letras, algumas com o sinal ¬, ligadas pela palavra “ou”. E nenhuma delas tem mais de três letras. O problema em que temos condições desse tipo e procuramos como atribuir verdadeiro e falso às letras para que todas valham ao mesmo tempo se chama 3-SAT. O três indica que cada condição tem no máximo três letras, e SAT é a abreviação do inglês satisfiability, satisfatibilidade.

À primeira vista, parece um passatempo de revista. Só que uma quantidade enorme de problemas práticos pode ser reescrita na forma 3-SAT: grades de horários escolares, a verificação de que um chip de processador calcula corretamente, o planejamento de escalas de trabalho e até o sudoku. Aí as letras não são quatro, mas tranquilamente milhões.

Quantas possibilidades é preciso testar?

O método mais direto é testar tudo. O Thiago vem ou não vem: são duas possibilidades. Para cada uma delas, o João vem ou não vem: já são quatro possibilidades. Para quatro amigos, são

$$2\cdot 2\cdot 2\cdot 2=2^4=16.$$

Foi o mesmo raciocínio que usamos com os vetores binários no artigo sobre P versus NP. Se temos n letras, podemos atribuir a elas verdadeiro e falso de 2ⁿ maneiras. Para 4 amigos são 16 possibilidades, que você percorre em poucos minutos. Para 100 letras são

$$2^{100}\approx 1,27\cdot {10}^{30}$$

possibilidades. Se um computador testasse um bilhão de possibilidades por segundo, precisaria de cerca de três mil vezes mais tempo do que a idade do universo.

Mas, ao contrário, é fácil: se alguém disser a você “convide estes três”, você confere na hora. Basta percorrer as seis condições e ver se cada uma vale. Encontrar a solução é difícil, conferir é fácil. Foi exatamente esse tipo de problema que, no artigo sobre P versus NP, colocamos na classe NP.

Só que o 3-SAT não é um problema qualquer de NP: em 1971, mostrou-se que qualquer problema de NP pode ser traduzido para o 3-SAT. Então quem conseguisse resolver o 3-SAT rapidamente conseguiria resolver rapidamente absolutamente tudo o que dá para conferir rapidamente. Problemas com essa propriedade são chamados de NP-completos, e o 3-SAT é o representante mais famoso deles.

Dá para fazer mais rápido que 2ⁿ?

Dá. Testar absolutamente tudo é desnecessário. Basta perceber, por exemplo, que, se o Thiago não vier, da primeira condição segue imediatamente que a Karina precisa vir. Todas as possibilidades em que nenhum dos dois viria nós descartamos de cara. Algoritmos espertos combinam toda uma série de truques desse tipo. Os melhores conhecidos hoje precisam de cerca de

$${\mathrm{1,307}}^n$$

passos. É um salto enorme. Para n = 100, em vez de 10³⁰ saem cerca de 4,2 · 10¹¹ passos, o que um computador faz em poucos minutos.

Mas cuidado, aqui está a armadilha. 1,307ⁿ continua sendo uma função exponencial. Diminuímos a base de dois para 1,307, mas a variável n continuou no expoente. Se n continuar crescendo, no fim isso vai nos atropelar do mesmo jeito. Para n = 1000, até 1,307ⁿ é um número com 117 algarismos.

E como seria um algoritmo que não fosse exponencial? Por exemplo, um que se virasse com n³ passos. Ele seria polinomial, e o 3-SAT pertenceria então à classe P. Entre os polinômios e as exponenciais, porém, ainda existe uma zona cinzenta: funções que crescem mais rápido que qualquer polinômio e, mesmo assim, mais devagar que qualquer exponencial. Por exemplo,

$$2^{\sqrt{n}}.$$

Aqui, no expoente, há só a raiz quadrada de n. Vamos comparar as quatro funções em uma tabela:

Para n = 1000, $2^{\sqrt{n}}$ joga na mesma liga que n³, enquanto as duas exponenciais dispararam para números que nem têm nome. Funções como $2^{\sqrt{n}}$, que crescem mais devagar que cⁿ para qualquer base c maior que um, são chamadas de subexponenciais.

O gráfico mostra a mesma coisa. O eixo vertical é logarítmico: cada divisão para cima significa um número cem mil vezes maior. Caso contrário, nada além de 2ⁿ caberia na figura.

Em um gráfico assim, as exponenciais são retas que sobem sem parar. A vermelha 2ⁿ é mais inclinada que a laranja 1,307ⁿ, mas as duas são retas. O curioso é que a laranja, no começo, fica até abaixo da verde n³. Ela só a ultrapassa por volta de n = 42, mas daí em diante para sempre. Já a azul $2^{\sqrt{n}}$ vai se curvando e fica lá embaixo, perto da verde.

O que exatamente a ETH afirma

Agora já podemos enunciar a hipótese. Ela foi formulada em 1999 por Russell Impagliazzo e Ramamohan Paturi:

Existe um número c maior que um tal que nenhum algoritmo consegue resolver o 3-SAT com n letras mais rápido que em cerca de cⁿ passos.

E em linguagem simples? A base da exponencial nós conseguimos diminuir com truques espertos: de dois para 1,5, para 1,307, talvez um dia para 1,2. Mas nunca vamos conseguir aproximá-la de um tanto quanto quisermos. Em algum lugar há um limite abaixo do qual não dá para descer. Então, segundo a ETH, um algoritmo com complexidade $2^{\sqrt{n}}$ não deveria existir.

Por que hipótese? Porque ninguém sabe demonstrá-la. A ETH é uma suposição de trabalho, parecida com o que fazemos no artigo sobre P versus NP ao supor que P ≠ NP. A maioria dos cientistas da computação acredita nela, porque décadas de esforço só conseguiram fazer a base ir descendo devagar a partir do dois. Mas ninguém tem uma demonstração em mãos.

A ETH e P versus NP

Como essas duas questões se relacionam? Imagine que o 3-SAT tenha uma dificuldade “real”, o algoritmo mais rápido possível. Ele pode estar em três faixas:

• Faixa verde, polinomial. O 3-SAT pode ser resolvido, por exemplo, em n³ passos. Como o 3-SAT é NP-completo, valeria então P = NP, e a ETH, claro, não valeria.
• Faixa azul, subexponencial. O 3-SAT pode ser resolvido em $2^{\sqrt{n}}$ passos ou algo parecido. Em tempo polinomial não, então vale P ≠ NP. Mas a ETH não valeria.
• Faixa vermelha, exponencial. Não dá para fazer melhor que cⁿ. A ETH vale e, consequentemente, também vale P ≠ NP.

Pela figura, dá para ver que a ETH é uma afirmação mais forte que P ≠ NP. Ela não diz apenas que o 3-SAT não pode ser resolvido em tempo polinomial, mas que não pode ser resolvido nem em tempo subexponencial. Quem demonstrasse a ETH demonstraria com isso também P ≠ NP e ganharia um milhão de dólares.

E, ao contrário, quem refutasse a ETH não teria necessariamente demonstrado P = NP. Basta a ele um algoritmo da faixa azul. Guarde isso, vamos usar daqui a pouco.

Para que serve a ETH

Demonstrar que um problema não pode ser resolvido rapidamente é incrivelmente difícil na computação. Quase nunca sabemos fazer isso. A ETH nos dá uma porta dos fundos: em vez de “o problema X é difícil”, demonstramos “o problema X é difícil se a ETH valer”.

Como? Mostramos que, se o problema X pudesse ser resolvido rapidamente, o 3-SAT também poderia. Pegue, por exemplo, este: temos n pessoas e sabemos que alguns pares delas não se suportam. Queremos distribuí-las em três salas de modo que nenhum desses pares fique na mesma sala. Os cientistas da computação chamam isso de coloração de um grafo com três cores. A partir de qualquer problema 3-SAT dá para construir um desses de modo que o número de pessoas seja só um pequeno múltiplo do número de letras. Então, se desse para distribuir as pessoas nas salas em tempo subexponencial, daria para resolver o 3-SAT em tempo subexponencial também, e a ETH cairia.

Hoje existem centenas de resultados condicionais assim. Toda uma área, que estuda exatamente quão difíceis são os diferentes problemas, se apoia na ETH como uma casa nos alicerces.

A ETH tem também uma irmã mais forte, a hipótese forte do tempo exponencial (SETH). Ela trata de problemas em que as condições podem ter mais de três letras, por exemplo dez ou cem. A SETH afirma que, quanto mais longas forem as condições permitidas, mais a melhor base possível se aproxima de dois. Para condições longas, portanto, não daria para economizar quase nada em comparação com testar na força bruta todas as 2ⁿ possibilidades.

Por que se fala da ETH agora

A empresa OpenAI, que você conhece principalmente pelo ChatGPT, publicou em outubro de 2026 um preprint, ou seja, um artigo que ainda não passou por revisão por pares. Ele se chama The Exponential Time Hypothesis is False, em português “A hipótese do tempo exponencial é falsa”. Nele, a empresa afirma ter encontrado um algoritmo que resolve o 3-SAT em cerca de

$$2^{\frac{n}{\sqrt{\ln n}}}$$

passos. No expoente, portanto, não está o n sozinho, mas n dividido pela raiz quadrada do logaritmo (natural). Esse denominador cresce terrivelmente devagar, mas cresce, e isso basta para que a função seja subexponencial. Segundo o artigo, o algoritmo consegue não só encontrar uma solução, mas até contar quantas soluções existem.

Se isso fosse verdade, o algoritmo da OpenAI cairia na faixa azul da figura lá em cima. E o que isso significaria?

• A ETH cairia, e com ela também a SETH e as centenas de resultados condicionais que se apoiavam nelas. Os cientistas da computação teriam que jogar fora ou reescrever um monte de “se a ETH valer, então…”.
• O problema P versus NP não seria resolvido. O algoritmo continua não sendo polinomial.
• Na prática, quase nada mudaria. Na fórmula se escondem constantes que não conhecemos. Se elas fossem iguais a um, para n = 1000 teríamos $\sqrt{\ln n}$ aproximadamente igual a 2,6 e obteríamos cerca de 2³⁸⁰ passos. Isso é quase o mesmo que 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ dos melhores algoritmos atuais. O novo algoritmo só superaria claramente os atuais para n ainda maiores, e por quanto depende justamente das constantes desconhecidas. Ele tem, portanto, principalmente importância teórica. A criptografia e os bancos não são afetados.

Por enquanto, trata-se de uma afirmação não verificada. A demonstração é longa e técnica, e os especialistas estão só começando a lê-la. No passado, grandes anúncios de problemas resolvidos já se mostraram errados muitas vezes, então, por enquanto, vale esperar para ver o que os especialistas vão dizer. Escrevemos este parágrafo em 27 de outubro de 2026.

Solução do problema da festa

Você deve convidar o Thiago, o João e o Daniel, mas não a Karina. Na figura estão todas as 16 possibilidades. Cada coluna é uma possibilidade: a bolinha cheia significa que o amigo vem, a vazia, que não vem. O número vermelho embaixo da coluna mostra a primeira condição que não vale. A única possibilidade em que todas as condições valem está destacada com uma moldura verde.

E é exatamente essa força bruta que a ETH considera quase insuperável: para quatro amigos, dezesseis colunas; para cem amigos, mais colunas do que átomos no nosso corpo.

Veja também

• O maior problema da computação: P versus NP
• Lógica proposicional
• Função exponencial
• Crescimento exponencial