OpenAI și Anthropic au publicat fiecare câte o demonstrație că ipoteza timpului exponențial este falsă.
ETH este o presupunere veche de 27 de ani din informatica teoretică, care spune că unele probleme nu pot fi rezolvate mult mai rapid decât prin forță brută. Acum, cele mai importante laboratoare de AI afirmă că pur și simplu nu e adevărat.
Dacă demonstrațiile rezistă, ele sunt cel mai semnificativ rezultat generat de AI în informatică de până acum. Forțează, de asemenea, o reconsiderare a literalmente sute de lucrări de cercetare care au presupus că ETH este adevărată.
În acest articol, explicăm ce înseamnă de fapt ipoteza timpului exponențial, împreună cu P vs. NP, care este înrudită. Vom analiza, de asemenea, ce afirmă exact cele două laboratoare, cum au fost verificate demonstrațiile și ce se schimbă (și ce nu) pentru criptografie.
P vs. NP, pe înțelesul tuturor
P versus NP întreabă dacă fiecare problemă al cărei răspuns este ușor de verificat este și ușor de rezolvat. Este una dintre cele șapte Probleme ale Mileniului, iar ea rămâne deschisă după aceste vești.
Un puzzle Sudoku este ilustrarea clasică. Verificarea unei grile completate durează câteva secunde: scanezi fiecare rând, coloană și chenar pentru repetiții. Găsirea soluției dintr-o grilă aproape goală poate dura mult mai mult, iar diferența explodează pe măsură ce grila crește.
- P este clasa problemelor pe care un calculator le poate rezolva în timp polinomial, adică munca crește ca n², n³ și așa mai departe, pe măsură ce dimensiunea intrării n crește.
- NP este clasa problemelor ale căror soluții propuse un calculator le poate verifica în timp polinomial.
Orice problemă din P este și în NP. Întrebarea deschisă este dacă și inversul e valabil. Majoritatea informaticienilor cred că P ≠ NP, astfel încât unele probleme sunt fundamental mai greu de rezolvat decât de verificat. Criptografia modernă se sprijină pe această credință: criptarea e ușoară, dar desfacerea ei fără cheie ar trebui să fie dificilă.
Ce este Ipoteza timpului exponențial?
ETH este mai strictă: afirmă că o anumită problemă NP, 3-SAT, are nevoie de timp exponențial indiferent cât de ingenios e algoritmul. Russell Impagliazzo și Ramamohan Paturi de la UC San Diego au propus-o la sfârșitul anilor 1990, cu contribuții fundamentale de la Francis Zane.
Problema 3-SAT
În 3-SAT, primești o formulă alcătuită din n variabile adevărat/fals și o listă de clauze. Fiecare clauză unește trei condiții cu SAU (OR), de exemplu „x₁ este adevărat SAU x₄ este fals SAU x₇ este adevărat”. Sarcina este să găsești o atribuire a variabilelor care să satisfacă toate clauzele deodată.
Forța brută încearcă toate cele 2ⁿ atribuiri, astfel că fiecare variabilă în plus dublează munca. Poți vedea cum pe la 100 de variabile acest lucru devine fără speranță.
Ce spune ETH
ETH afirmă că există o constantă c > 1 astfel încât niciun algoritm nu rezolvă 3-SAT mai repede decât cⁿ. Algoritmii ingenioși pot micșora baza sub 2, dar niciodată până la ceva subexponențial. Formal: există δ > 0 astfel încât 3-SAT nu poate fi rezolvat în timp O(2δn).
Decenii la rând, progresul a corespuns acestei imagini. Cercetătorii tot reduceau baza, dar rămânea mult peste 1. Deoarece 3-SAT poate fi convertită în multe alte probleme, ETH a devenit o presupunere de lucru. Cercetătorii au folosit-o pentru a argumenta că probleme precum Clique, Acoperire de vârfuri (Vertex Cover), Mulțime independentă și altele nu pot fi nici ele rezolvate mult mai rapid.
Cum se compară noul rezultat
| Abordare | Timp de rulare pentru 3-SAT | Crește exponențial? |
|---|
| Forță brută | 2ⁿ | Da |
| Cea mai bună cunoscută înainte de oct. 2026 (determinist) | aprox. 1,328ⁿ | Da |
| Cea mai bună cunoscută înainte de oct. 2026 (randomizat) | aprox. 1,308ⁿ | Da |
| OpenAI și Anthropic (oct. 2026) | 2^O(n log log n / √log n) | Nu: subexponențial |
Noul plafon se scrie pe scurt 2o(n). Costul per variabilă adăugată scade spre 1 pe măsură ce n crește, exact ceea ce ETH spunea că e imposibil.
Ce au anunțat OpenAI și Anthropic
Ambele laboratoare au ajuns independent, în esență, la același plafon subexponențial și ambele și-au susținut lucrările cu demonstrații verificate automat în asistentul de demonstrații Lean.
| | OpenAI | Anthropic |
|---|
| Lucrare | „The Exponential Time Hypothesis Is False” (67 pagini) | „A 2o(n) Time Algorithm for 3-SAT” (49 pagini) |
| Model | Model intern fără nume | Model intern Claude de cercetare, creditat ca autor |
| Ideea de bază găsită | 16 octombrie 2026 | 16 octombrie 2026 |
| Făcut public | 26 octombrie 2026 | 26–27 octombrie 2026 |
| Verificare | Demonstrație în Lean a unui plafon ușor mai slab care tot infirmă ETH | Demonstrație în Lean 4 contra Mathlib, reverificată de un al doilea nucleu |
| Afirmații suplimentare | Accelerarea nu se extinde la tot NP | Infirmă și ETH tare (SETH); nouă bornă inferioară pentru circuite |
Anthropic spune că Claude a găsit algoritmul de bază fără intervenție umană după ce a produs aproximativ 14 milioane de tokeni de ieșire. Metoda folosește rețele tensoriale și argumente de rang. Cercetătorii au ajutat apoi la definitivarea lucrării.
De ce ambele laboratoare l-au găsit în aceeași zi?
Niciun laborator nu a explicat sincronizarea. Lucrarea Anthropic numește cele două rezultate independente și concurrente, iar cele două expuneri parcurg căi diferite prin matematică pentru a ajunge la esențial același plafon.
Un context face suprapunerea mai puțin surprinzătoare decât pare la început. Ambele laboratoare își orientează modelele către liste lungi de probleme deschise, iar OpenAI singură a publicat sute de manuscrise de matematică generate de AI la începutul lui octombrie. ETH este una dintre țintele cele mai cunoscute din domeniu, iar ambele modele au învățat din aceeași cercetare publicată. Descoperirea independentă și simultană este, de asemenea, un tipar vechi în știință, ca în cazul lui Newton și Leibniz la calcul sau Darwin și Wallace la selecția naturală.
Cât de solide sunt demonstrațiile?
Lean confirmă că o afirmație formală decurge logic din axiomele sale. Nu poate confirma că afirmația formală spune același lucru ca lucrarea. Anthropic remarcă faptul că nicio mașină nu verifică această corespondență, iar OpenAI spune că fișierul său Lean demonstrează un plafon ușor mai slab decât titlul.
Acum, aceiași cercetători care au propus problema, Impagliazzo și Paturi, împreună cu Ryan Williams de la MIT, organizează ateliere pentru a evalua dacă afirmațiile formale chiar surprind ETH. Scrisoarea lor subliniază că participarea la revizuire nu este o aprobare. Până în acest moment, la scrierea articolului, nimeni nu a găsit public o eroare.
Williams a spus că părți din demonstrația OpenAI par de rutină, în timp ce „două sau trei părți cu aspect extraterestru” încă necesită analiză. Impagliazzo, unul dintre autorii ETH, a descris rezultatul ca fiind profund surprinzător.
Ce se schimbă și ce nu
În practică, aproape nimic nu se schimbă astăzi (uf): noile algoritmi depășesc forța brută doar pe intrări mult mai mari decât ar putea vreodată să încapă într-un calculator.
Nu există rezolvatoare SAT mai rapide
Lucrarea Anthropic spune că metoda sa depășește forța brută doar pe intrări astronomic de mari. Pentru formule tipice cu cinci clauze pe variabilă, punctul de intersecție este un număr cu aproximativ 10.000 de cifre. În cel mai general caz, este un număr cu aproximativ 100 de milioane de cifre.
Autorii mai spun că abordarea lor e puțin probabil să ajute la orice sub aproximativ 10 milioane de variabile. Rezolvatoarele SAT folosite în verificarea de cipuri, programare și planificare nu vor deveni mai rapide datorită acestui rezultat.
Criptografia nu e compromisă
Rezultatul nu atinge P vs NP. Nimeni nu pretinde asta. OpenAI spune că a verificat dacă algoritmul sparge criptosisteme reale și este destul de încrezător că nu o face.
Teoria se rescrie
Impactul mai mare este asupra cercetării. Rezultatele de duritate construite pe ETH sau SETH au nevoie acum de un nou fundament, iar unii cercetători au spus că ani din propria lor muncă ar putea necesita revizuire. Nu totul cade, totuși. Anthropic observă că rezultatul nu infirmă problema vectorilor ortogonali, care susține multe rezultate de complexitate cu granulație fină.
De ce contează pentru AI
Titlul este mai puțin despre 3-SAT și mai mult despre cine a găsit răspunsul: două sisteme AI au răsturnat independent o conjectură în care experții umani au avut încredere o generație.
AI ca partener de cercetare
Cercetătorii descriu acum rezultate noi de AI care apar la fiecare săptămână sau două, perturbând proiecte deja în curs. Instrumentele formale precum Lean devin centrale pentru că le permit oamenilor să aibă încredere într-o demonstrație lungă scrisă de o mașină fără a re-deriva fiecare linie.
Scurtături ascunse și auto-îmbunătățire
ETH surprindea credința că unele probleme de căutare nu au nicio scurtătură ingenioasă. Dacă acea credință este greșită, și alte probleme în mod evident dificile pot ascunde scurtături.
Mă gândesc la descoperirea de algoritmi ca la o zonă în care astfel de scurtături ar putea conta mult pentru auto-îmbunătățirea recursivă, adică ideea unor sisteme AI care ajută la proiectarea unui AI mai bun. Folosirea AI pentru a găsi algoritmi mai rapizi este o cale concretă în această direcție, deși nimic din acest rezultat nu face asta direct astăzi.
Ce înseamnă pentru practicienii din date
Pentru cei care construiesc cu date, trei lecții ies în evidență:
- Teoria complexității nu e doar academică: Să știi de ce o problemă este NP-grea îți spune când să te gândești la euristici, aproximații sau rezolvatoare, în locul căutării exacte.
- Verificarea este o abilitate: Pe măsură ce AI generează mai mult cod și analiză, verificarea rezultatului (cu teste, demonstrații sau fluxuri reproductibile) contează la fel de mult ca producerea lui.
- Asimptotica poate induce în eroare: Un algoritm „mai rapid” în teorie poate fi inutil la dimensiuni din lumea reală.
Concluzie
Dacă demonstrațiile trec de revizuirea experților, ipoteza timpului exponențial se va alătura scurtei liste de conjecturi larg crezute care s-au dovedit false (precum conjectura lui Euler despre suma puterilor). Dar P vs NP rămâne deschisă și criptografia este în siguranță pentru moment.
Următoarele repere de urmărit sunt atelierele de revizuire conduse de autorii originali ai ETH, reimplementări independente ale algoritmilor și dacă cineva strânge și mai mult plafonul.
Pentru a construi fundamentele din spatele unor povești ca aceasta, explorează cursurile noastre despre structuri de date și algoritmi, programare în Python și machine learning. Ele acoperă gândirea în termeni de Big-O care face ca rezultate ca acesta să fie lizibile.
OpenAI și Anthropic au publicat fiecare câte o demonstrație că ipoteza timpului exponențial este falsă.
ETH este o presupunere veche de 27 de ani din informatica teoretică, care spune că unele probleme nu pot fi rezolvate mult mai rapid decât prin forță brută. Acum, cele mai importante laboratoare de AI afirmă că pur și simplu nu e adevărat.
Dacă demonstrațiile rezistă, ele sunt cel mai semnificativ rezultat generat de AI în informatică de până acum. Forțează, de asemenea, o reconsiderare a literalmente sute de lucrări de cercetare care au presupus că ETH este adevărată.
În acest articol, explicăm ce înseamnă de fapt ipoteza timpului exponențial, împreună cu P vs. NP, care este înrudită. Vom analiza, de asemenea, ce afirmă exact cele două laboratoare, cum au fost verificate demonstrațiile și ce se schimbă (și ce nu) pentru criptografie.
P vs. NP, pe înțelesul tuturor
P versus NP întreabă dacă fiecare problemă al cărei răspuns este ușor de verificat este și ușor de rezolvat. Este una dintre cele șapte Probleme ale Mileniului, iar ea rămâne deschisă după aceste vești.
Un puzzle Sudoku este ilustrarea clasică. Verificarea unei grile completate durează câteva secunde: scanezi fiecare rând, coloană și chenar pentru repetiții. Găsirea soluției dintr-o grilă aproape goală poate dura mult mai mult, iar diferența explodează pe măsură ce grila crește.
Orice problemă din P este și în NP. Întrebarea deschisă este dacă și inversul e valabil. Majoritatea informaticienilor cred că P ≠ NP, astfel încât unele probleme sunt fundamental mai greu de rezolvat decât de verificat. Criptografia modernă se sprijină pe această credință: criptarea e ușoară, dar desfacerea ei fără cheie ar trebui să fie dificilă.
Ce este Ipoteza timpului exponențial?
ETH este mai strictă: afirmă că o anumită problemă NP, 3-SAT, are nevoie de timp exponențial indiferent cât de ingenios e algoritmul. Russell Impagliazzo și Ramamohan Paturi de la UC San Diego au propus-o la sfârșitul anilor 1990, cu contribuții fundamentale de la Francis Zane.
Problema 3-SAT
În 3-SAT, primești o formulă alcătuită din n variabile adevărat/fals și o listă de clauze. Fiecare clauză unește trei condiții cu SAU (OR), de exemplu „x₁ este adevărat SAU x₄ este fals SAU x₇ este adevărat”. Sarcina este să găsești o atribuire a variabilelor care să satisfacă toate clauzele deodată.
Forța brută încearcă toate cele 2ⁿ atribuiri, astfel că fiecare variabilă în plus dublează munca. Poți vedea cum pe la 100 de variabile acest lucru devine fără speranță.
Ce spune ETH
ETH afirmă că există o constantă c > 1 astfel încât niciun algoritm nu rezolvă 3-SAT mai repede decât cⁿ. Algoritmii ingenioși pot micșora baza sub 2, dar niciodată până la ceva subexponențial. Formal: există δ > 0 astfel încât 3-SAT nu poate fi rezolvat în timp O(2δn).
Decenii la rând, progresul a corespuns acestei imagini. Cercetătorii tot reduceau baza, dar rămânea mult peste 1. Deoarece 3-SAT poate fi convertită în multe alte probleme, ETH a devenit o presupunere de lucru. Cercetătorii au folosit-o pentru a argumenta că probleme precum Clique, Acoperire de vârfuri (Vertex Cover), Mulțime independentă și altele nu pot fi nici ele rezolvate mult mai rapid.
Cum se compară noul rezultat
Noul plafon se scrie pe scurt 2o(n). Costul per variabilă adăugată scade spre 1 pe măsură ce n crește, exact ceea ce ETH spunea că e imposibil.
Ce au anunțat OpenAI și Anthropic
Ambele laboratoare au ajuns independent, în esență, la același plafon subexponențial și ambele și-au susținut lucrările cu demonstrații verificate automat în asistentul de demonstrații Lean.
Anthropic spune că Claude a găsit algoritmul de bază fără intervenție umană după ce a produs aproximativ 14 milioane de tokeni de ieșire. Metoda folosește rețele tensoriale și argumente de rang. Cercetătorii au ajutat apoi la definitivarea lucrării.
De ce ambele laboratoare l-au găsit în aceeași zi?
Niciun laborator nu a explicat sincronizarea. Lucrarea Anthropic numește cele două rezultate independente și concurrente, iar cele două expuneri parcurg căi diferite prin matematică pentru a ajunge la esențial același plafon.
Un context face suprapunerea mai puțin surprinzătoare decât pare la început. Ambele laboratoare își orientează modelele către liste lungi de probleme deschise, iar OpenAI singură a publicat sute de manuscrise de matematică generate de AI la începutul lui octombrie. ETH este una dintre țintele cele mai cunoscute din domeniu, iar ambele modele au învățat din aceeași cercetare publicată. Descoperirea independentă și simultană este, de asemenea, un tipar vechi în știință, ca în cazul lui Newton și Leibniz la calcul sau Darwin și Wallace la selecția naturală.
Cât de solide sunt demonstrațiile?
Lean confirmă că o afirmație formală decurge logic din axiomele sale. Nu poate confirma că afirmația formală spune același lucru ca lucrarea. Anthropic remarcă faptul că nicio mașină nu verifică această corespondență, iar OpenAI spune că fișierul său Lean demonstrează un plafon ușor mai slab decât titlul.
Acum, aceiași cercetători care au propus problema, Impagliazzo și Paturi, împreună cu Ryan Williams de la MIT, organizează ateliere pentru a evalua dacă afirmațiile formale chiar surprind ETH. Scrisoarea lor subliniază că participarea la revizuire nu este o aprobare. Până în acest moment, la scrierea articolului, nimeni nu a găsit public o eroare.
Williams a spus că părți din demonstrația OpenAI par de rutină, în timp ce „două sau trei părți cu aspect extraterestru” încă necesită analiză. Impagliazzo, unul dintre autorii ETH, a descris rezultatul ca fiind profund surprinzător.
Ce se schimbă și ce nu
În practică, aproape nimic nu se schimbă astăzi (uf): noile algoritmi depășesc forța brută doar pe intrări mult mai mari decât ar putea vreodată să încapă într-un calculator.
Nu există rezolvatoare SAT mai rapide
Lucrarea Anthropic spune că metoda sa depășește forța brută doar pe intrări astronomic de mari. Pentru formule tipice cu cinci clauze pe variabilă, punctul de intersecție este un număr cu aproximativ 10.000 de cifre. În cel mai general caz, este un număr cu aproximativ 100 de milioane de cifre.
Autorii mai spun că abordarea lor e puțin probabil să ajute la orice sub aproximativ 10 milioane de variabile. Rezolvatoarele SAT folosite în verificarea de cipuri, programare și planificare nu vor deveni mai rapide datorită acestui rezultat.
Criptografia nu e compromisă
Rezultatul nu atinge P vs NP. Nimeni nu pretinde asta. OpenAI spune că a verificat dacă algoritmul sparge criptosisteme reale și este destul de încrezător că nu o face.
Teoria se rescrie
Impactul mai mare este asupra cercetării. Rezultatele de duritate construite pe ETH sau SETH au nevoie acum de un nou fundament, iar unii cercetători au spus că ani din propria lor muncă ar putea necesita revizuire. Nu totul cade, totuși. Anthropic observă că rezultatul nu infirmă problema vectorilor ortogonali, care susține multe rezultate de complexitate cu granulație fină.
De ce contează pentru AI
Titlul este mai puțin despre 3-SAT și mai mult despre cine a găsit răspunsul: două sisteme AI au răsturnat independent o conjectură în care experții umani au avut încredere o generație.
AI ca partener de cercetare
Cercetătorii descriu acum rezultate noi de AI care apar la fiecare săptămână sau două, perturbând proiecte deja în curs. Instrumentele formale precum Lean devin centrale pentru că le permit oamenilor să aibă încredere într-o demonstrație lungă scrisă de o mașină fără a re-deriva fiecare linie.
Scurtături ascunse și auto-îmbunătățire
ETH surprindea credința că unele probleme de căutare nu au nicio scurtătură ingenioasă. Dacă acea credință este greșită, și alte probleme în mod evident dificile pot ascunde scurtături.
Mă gândesc la descoperirea de algoritmi ca la o zonă în care astfel de scurtături ar putea conta mult pentru auto-îmbunătățirea recursivă, adică ideea unor sisteme AI care ajută la proiectarea unui AI mai bun. Folosirea AI pentru a găsi algoritmi mai rapizi este o cale concretă în această direcție, deși nimic din acest rezultat nu face asta direct astăzi.
Ce înseamnă pentru practicienii din date
Pentru cei care construiesc cu date, trei lecții ies în evidență:
Concluzie
Dacă demonstrațiile trec de revizuirea experților, ipoteza timpului exponențial se va alătura scurtei liste de conjecturi larg crezute care s-au dovedit false (precum conjectura lui Euler despre suma puterilor). Dar P vs NP rămâne deschisă și criptografia este în siguranță pentru moment.
Următoarele repere de urmărit sunt atelierele de revizuire conduse de autorii originali ai ETH, reimplementări independente ale algoritmilor și dacă cineva strânge și mai mult plafonul.
Pentru a construi fundamentele din spatele unor povești ca aceasta, explorează cursurile noastre despre structuri de date și algoritmi, programare în Python și machine learning. Ele acoperă gândirea în termeni de Big-O care face ca rezultate ca acesta să fie lizibile.