# Anche Anthropic dichiara falsa l'ETH: l'algoritmo per 3-SAT trovato da Claude

_Poche ore dopo OpenAI, Anthropic pubblica paper, prova Lean e preprint: un algoritmo subesponenziale per 3-SAT trovato da un modello Claude interno. Cosa dice, cosa è controllato e perché resta da verificare._

Fonte: https://andreapirazzini.it/blog/anthropic-claude-eth-falsa-3-sat-algoritmo-subesponenziale · 30 ottobre 2026

> Articolo redatto da un sistema di AI a partire da fonti ufficiali: https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth.

## In breve

- Il 27 ottobre 2026 Anthropic ha pubblicato «A 2^o(n) Time Algorithm for 3-SAT», firmato «Claude, Anthropic», con prova Lean e preprint su Hexagon.
- Secondo Anthropic l'algoritmo è stato trovato il 16 ottobre da un modello Claude interno, con 14 milioni di token e nessun input umano.
- È il secondo laboratorio, dopo OpenAI, a dichiarare l'ETH falsa: il paper parla di lavori indipendenti e in parallelo.
- La prova Lean ha 1.050 moduli, scritti e rivisti da modelli AI: nessuna persona risulta averla controllata.
- Il risultato è solo asintotico: batte la forza bruta oltre 10^10.000 variabili e non aiuta a risolvere formule nella pratica.

Il 27 ottobre 2026, poche ore dopo l'annuncio di OpenAI, anche **Anthropic** ha pubblicato un paper che dichiara falsa l'**Exponential Time Hypothesis** (ETH). Il titolo è «A 2^o(n) Time Algorithm for 3-SAT», la firma è «Claude, Anthropic»: secondo l'azienda l'algoritmo è stato trovato da un modello Claude interno di ricerca. È il secondo laboratorio in due giorni a sostenere lo stesso risultato. Ed è, come quello di OpenAI, una **dichiarazione non ancora verificata** dalla comunità scientifica.

> **Attenzione:** Quello che segue riporta ciò che Anthropic dichiara nel paper e nel repository ufficiale. Il risultato non è passato da revisione paritaria e, scrive Anthropic stessa, nessuna persona risulta aver controllato la prova formale in Lean.

- **16 ott** Giorno in cui Claude ha trovato l'algoritmo, secondo Anthropic
- **14 mln** Token in output usati dal modello, senza input umano
- **1.050** Moduli Lean della prova formale, scritta da modelli AI
- **800+** Articoli con risultati che poggiano sull'ETH, contati da Claude

_Fonte: Paper «A 2^o(n) Time Algorithm for 3-SAT» e repository github.com/anthropics/formal-math, verificati il 27/10/2026_

## Cosa ha pubblicato Anthropic

Tre cose, tutte pubbliche:

- il **paper** di 49 pagine, datato 26 ottobre 2026, nella cartella `eth` del repository ufficiale [anthropics/formal-math](https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth), aggiunta il 27 ottobre alle 04:07 ora di Roma;
- la **prova formale in Lean 4**, nella stessa cartella;
- il **preprint** su [Hexagon](https://hexagonmath.org/2610.00577v1), «Contributed by Anthropic», depositato il 27 ottobre da Jelani Nelson per conto dell'azienda.

L'abstract è netto: «We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in 2^o(n) time». E aggiunge che l'algoritmo risolve un problema più difficile, contare tutte le soluzioni (#3-SAT).

![La scheda del preprint su Hexagon: A 2^o(n) Time Algorithm for 3-SAT, Contributed by Anthropic, categoria Computational Complexity](https://xfzvzyxtnexwldhdjrdj.supabase.co/storage/v1/object/public/blog-media/posts/52e61bdd-a211-4875-a673-e581a25fc326/b1cc70b8-e474-427c-bafe-d9bddebe72c8.jpg)
*La scheda ufficiale del preprint su Hexagon. Immagine: Hexagon.*

## Cos'è l'ETH, in breve

Il problema **3-SAT** chiede se una formula logica con n variabili, scritta come insieme di clausole da tre termini, può essere resa vera. Provare tutte le combinazioni costa 2^n passi. L'ETH, proposta da Impagliazzo e Paturi, dice che non si può fare molto meglio: nel caso peggiore serve comunque un tempo esponenziale, 2^Ω(n). Il miglior algoritmo deterministico noto finora girava in circa 1,328^n.

Su questa ipotesi poggiano moltissimi risultati di complessità. Con una ricerca bibliografica fatta da Claude, scrive Anthropic, sono stati trovati **più di 800 articoli** che dimostrano almeno un risultato solo assumendo l'ETH o un'ipotesi che la implica.

## Cosa dichiara il paper

Il Teorema 1 descrive un algoritmo deterministico che conta le soluzioni di una formula in tempo circa 2^O(n · log log n / √log n). È meno di qualsiasi esponenziale 2^(δn), per quanto piccolo sia δ: per questo si parla di tempo **subesponenziale**, 2^o(n). Se il risultato regge, le conseguenze dichiarate sono molte:

- cade anche la **Strong ETH** (SETH), ma non l'ipotesi Orthogonal Vectors, su cui poggiano altri limiti inferiori;
- problemi come Independent Set, Clique, Vertex Cover e Dominating Set diventano risolvibili in O(2^(δn)) per ogni δ > 0;
- si ottiene un nuovo limite sui circuiti: la classe E^NP non ha circuiti booleani di dimensione lineare.

## Due laboratori, stesse date

Il dettaglio più curioso è la coincidenza. Secondo il paper, «the core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input». Lo stesso giorno, secondo OpenAI, il suo sistema scriveva la prova in linguaggio naturale della stessa tesi. Il paper di Anthropic lo riconosce: «Independently and concurrently, an internal model at OpenAI claims to have proven a similar result».

|  | Anthropic (Claude) | OpenAI |
| --- | --- | --- |
| Algoritmo o prova trovati | 16 ottobre | 16 ottobre (testo), 17 ottobre (Lean) |
| Pubblicazione | 27 ottobre, GitHub e Hexagon | 26 ottobre, GitHub e annuncio |
| Bound dichiarato | 2^O(n · log log n / √log n) | 2^(n / (log n)^(1/2+o(1))) |
| Prova Lean | Sì, 1.050 moduli | Sì |
| Verifica esterna annunciata | No | Gruppo di Impagliazzo, Paturi e Williams |

[Animazione: Le date dichiarate dai due laboratori, dal 16 al 27 ottobre 2026. Animazione con Clawd, la mascotte di Claude Code.](https://xfzvzyxtnexwldhdjrdj.supabase.co/storage/v1/object/public/blog-media/posts/52e61bdd-a211-4875-a673-e581a25fc326/4e7611d4-6640-446c-a952-85e7f4d1ca10.mp4)

Le persone, precisa Anthropic, sono intervenute dopo: «Anthropic researchers worked with Claude to improve the presentation, resulting in this paper». Il README aggiunge un dato interessante: Claude Opus 5.5, impostato su «high effort», riesce a ricavare la versione base del risultato partendo da una descrizione condensata che il repository riporta.

## Solo teoria, per ora

Anthropic è molto chiara su un punto: «The result is purely asymptotic and says nothing about solving formulas in practice». I numeri del paper lo mostrano:

- con formule da 5n clausole, il bound batte la forza bruta solo se **n supera 10^10.000**;
- il bound che dipende solo da n non la batte finché n non supera 10^(10^8);
- l'approccio generale difficilmente porta guadagni sotto **n = 10^7**, mentre la forza bruta è già impraticabile a n = 100.

Il paper scrive anche che il risultato «does not bear on the P vs NP question directly, nor does it yield any practical algorithms for NP-complete problems». Nessun solver diventa più veloce domani.

[Animazione: Quando il bound di Anthropic batte la forza bruta, misurato in cifre del numero di variabili. Animazione con Clawd, la mascotte di Claude Code.](https://xfzvzyxtnexwldhdjrdj.supabase.co/storage/v1/object/public/blog-media/posts/52e61bdd-a211-4875-a673-e581a25fc326/6564d579-7c40-4d3b-91cb-62823271c455.mp4)

## Cosa garantisce la prova in Lean

Lean è un programma che controlla le dimostrazioni passaggio per passaggio. L'Appendice E del paper descrive la verifica: la prova usa solo i tre assiomi standard ed è accettata dal kernel di Lean, dal controllore leanchecker modulo per modulo e, tramite Comparator, da un secondo kernel scritto in modo indipendente (nanoda). Tutti i 1.050 moduli sono stati compilati da zero.

Ci sono però tre limiti, e li scrive Anthropic stessa.

- **L'enunciato.** Che le definizioni formali dicano davvero ciò che devono dire «no machine can check; that is for the reader».
- **Chi l'ha scritta.** «The Lean development was written by AI models and reviewed by other instances of the same models; at the time of writing no person is known to have checked it».
- **Lo stato.** Il repository è un «research artifact», non mantenuto. Il preprint non è passato da revisione paritaria.

> **Nota:** Lean riduce molto il rischio di errori nei passaggi. Non sostituisce il lavoro degli esperti, che devono controllare che il teorema formale sia proprio l'ETH e non una versione diversa.

## Cosa cambia per chi lavora con l'AI

Per un'azienda, oggi, niente di pratico: lo dice il paper. Il segnale interessante è un altro. Due laboratori diversi mostrano modelli che producono risultati **controllabili da un programma**, non solo testi convincenti. È un'abitudine che vale anche fuori dalla ricerca: quando usate un assistente AI per numeri, analisi o codice, chiedete qualcosa che si possa ricontrollare, come fonti, test o calcoli da rifare.

> **Consiglio:** Nelle prossime settimane conviene guardare a tre cose: i commenti degli esperti di complessità sui due paper, eventuali correzioni nei repository di Anthropic e OpenAI, e un confronto tra i due algoritmi.

## Domande frequenti

**Anthropic ha davvero dimostrato che l'ETH è falsa?**

Lo dichiara, con un paper e una prova formale in Lean pubblici. Il risultato non è ancora stato rivisto né confermato dalla comunità scientifica, e nessuna persona risulta aver controllato la prova Lean.

**È lo stesso risultato di OpenAI?**

La tesi è la stessa: 3-SAT risolvibile in tempo subesponenziale. I bound dichiarati sono simili ma non identici. Il paper di Anthropic parla di lavori indipendenti e in parallelo; se gli algoritmi coincidano lo diranno gli esperti.

**Nessun umano ha partecipato?**

Secondo Anthropic il modello ha trovato l'algoritmo senza input umano. Poi i ricercatori hanno lavorato con Claude per migliorare la presentazione del paper.

**Questo rende i computer più veloci su problemi reali?**

No. Il risultato è solo asintotico: con formule tipiche batte la forza bruta solo oltre 10 alla 10.000 variabili. Il paper scrive che non dice nulla sulla soluzione delle formule nella pratica.

**Risolve il problema P contro NP?**

No. Il paper scrive che il risultato non riguarda direttamente la questione P contro NP.

## Fonti

- [Repository anthropics/formal-math, cartella eth](https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth): paper, README e prova Lean, commit del 27/10/2026.
- [Preprint su Hexagon, 2610.00577v1](https://hexagonmath.org/2610.00577v1), «Contributed by Anthropic», 27/10/2026.
- [Post di Levent Alpoge (Anthropic) su X](https://x.com/__alpoge__/status/2114930095009968506), 27/10/2026.
- Per il confronto: [repository openai/math](https://github.com/openai/math), con il manoscritto di OpenAI sull'ETH.

[Prenota una call con Andrea](https://andreapirazzini.it/prenota)