OpenAI anunță o descoperire surprinzătoare: o ipoteză acceptată de informaticieni de aproape trei decenii ar putea fi greșită

Adaugă-ne ca sursă preferată

Urmărește-ne în Discover

Anunțul a fost făcut luni, la câteva săptămâni după publicarea a sute de rezultate matematice generate de inteligența artificială. De această dată, OpenAI susține că modelele sale au obținut trei rezultate importante, în domenii distincte: analiza matematică, complexitatea algoritmilor și fizica cuantică, scrie Engadget.

O ipoteză veche de aproape 30 de ani ar putea fi infirmată

Cea mai surprinzătoare afirmație privește Exponential Time Hypothesis (ETH), o ipoteză formulată în anii 1990. Aceasta pornește de la ideea că anumite probleme de calcul sunt atât de dificile încât timpul necesar rezolvării lor crește foarte rapid odată cu dimensiunea problemei. Ipoteza a fost utilizată în sute de lucrări științifice, inclusiv în cercetări privind bazele de date, biologia computațională și algoritmii.

România rămâne printre țările cu cele mai periculoase drumuri din UE. Doar Bulgaria are o rată mai mare a deceselor

Imagini spectaculoase în Rahova: etajele superioare ale blocului distrus de explozie s-au prăbușit în timpul lucrărilor

OpenAI afirmă că modelul său a construit o demonstrație care infirmă ETH, folosind un algoritm capabil să rezolve o categorie importantă de probleme într-un timp mai mic decât cel presupus anterior. Dacă rezultatul se confirmă, cercetătorii ar putea reconsidera limitele unor metode de calcul și ar putea căuta algoritmi mai eficienți.

The strong exponential time hypothesis (SETH) explained by MIT professor @rrwilliams who was selected by OpenAI to verify the recent breakthrough result:

Q: „Could you explain the Strong Exponential Time Hypothesis, or SETH, and its significance?”

Ryan Williams: „Strong ETH is a severe strengthening of the P versus NP question. P versus NP is asking whether the SAT problem has a polynomial-time algorithm or not.

Strong ETH is basically saying that for the SAT problem, you cannot solve it much faster than 2^n. There’s no 1.999^n time algorithm. For every string of 9s, there is no 1.9999^n time algorithm. To say it totally precisely, it has to do with the k-SAT problem, where you’re looking at clauses of length k for arbitrary k, but those details don’t matter so much.

SAT is a canonical NP-complete problem. It’s solved all the time in practice. It’s extremely useful for verification; nowadays it’s an engine for verification. So it can be solved fairly well in practice. However, in the worst case, we still don’t know how to solve it significantly faster than 2^n.

So the hypothesis that it needs, say, 1.99999^n time is a very strong exponential time hypothesis. It’s stronger than P versus NP. It says it’s not just superpolynomial. It’s darn near 2^n time that you need.”

Q: „Do you think that hypothesis is true? Why or why not?”

Ryan Williams: „I think I’m on the record as not believing this hypothesis.

Why don’t I believe it? I started thinking about this hypothesis maybe already as an undergrad, but certainly early in grad school. Before it was even called Strong ETH, I guess that shows how old I am. I was trying to figure out how to solve CNF-SAT faster than 2^n.

At the time there were a number of other NP-complete problems that had faster algorithms, like subset sum. So I thought, what’s so special about SAT? If all these other problems have faster algorithms, why not SAT as well?

Even 3-SAT, where each clause is an OR of 3 variables, has a faster algorithm, and this is just a more general version of SAT. So at first I thought there’s no good reason to believe a lower bound. These other related problems have upper bounds, so why not?

But then, over time, I would have different attacks on Strong ETH, always trying to refute it in different ways. These attacks would fail in some completely catastrophic and ridiculous way. They would have no chance of actually solving the original problem.

But by staring at my failure, I’d think: there’s something interesting happening here. It doesn’t refute Strong ETH, so what does it do? By trying to pivot and figure out what I could do with my failure, I was able to solve a variety of other problems instead.

So after a while, I realized that the truth value of Strong ETH to me is almost irrelevant. If I believe that it’s false, then I get good ideas.

By thinking about what an algorithm that breaks 2^n could look like, I force myself to think in a different way. I have to discard the natural algorithmic possibilities, because we know they won’t work, and think in a different direction. Because it sends my brain in a different direction, it’s very useful for research. Even though I still haven’t refuted it, it’s very useful for me to believe that it’s false, operationally.”

Q: This is a minority opinion, right?

Ryan Williams: „Russell Impagliazzo, a good friend of mine who helped propose this, always emphasizes to me: this is a hypothesis. We explicitly did not name it a conjecture. We wanted to put forth a lower bound that would get you to think about it, something a little more controversial than P versus NP or other things people more normally believe.

Hypotheses at the edge of our understanding, where we truly don’t know what the answer might be based on our intuition, can be enlightening to think about. That’s one reason why it was proposed.

But one reason you might believe Strong ETH is true is that it conveniently implies a lot of other lower bounds. You can reduce SAT to a bunch of problems that seem totally unrelated, like edit distance and various pattern matching problems. They have natural polynomial-time solutions. If you could improve on the algorithms for any of those, you would improve the one for SAT as well, and get something better than 2^n.

So believing in it makes a convenient worldview. It shows that all these different textbook algorithms are indeed optimal.”

— Ryan Peterman (@ryanlpeterman) October 27, 2026

Acest lucru nu înseamnă însă că toate problemele informatice dificile vor putea fi rezolvate rapid sau că ipoteza P versus NP a fost soluționată. Demonstrația a fost publicată pentru verificare, iar printre experții implicați se numără Russell Impagliazzo și Ramamohan Paturi, doi dintre cercetătorii care au formulat inițial ipoteza.

O nouă demonstrație pentru comportamentul undelor

În matematică, OpenAI susține că a rezolvat o problemă formulată în 1991 de matematicianul Christopher Sogge. Aceasta privește modul în care undele se concentrează și se propagă, o întrebare importantă în analiza ecuațiilor matematice care descriu asemenea fenomene.

Potrivit companiei, demonstrația acoperă toate dimensiunile spațiale relevante și ar permite rezolvarea altor două conjecturi cunoscute, asociate problemelor Kakeya și Stein.

Materialele au fost publicate pe GitHub, inclusiv într-o formă verificabilă cu ajutorul sistemului matematic Lean. Verificarea formală reprezintă un pas important, dar cercetătorii urmează să examineze și ipotezele, explicațiile și semnificația rezultatelor.

Fizica cuantică, a treia direcție de cercetare

OpenAI anunță și demonstrații privind existența matematică a unor teorii cuantice ale câmpurilor în patru dimensiuni. Printre acestea se numără cromodinamica cuantică, teoria care descrie interacțiunile dintre quarcuri și gluoni. Lucrările includ și un rezultat privind teoria Yang-Mills, asociată uneia dintre cele șapte Probleme ale Mileniului.

Totuși, compania nu susține că ar fi rezolvat integral problema premiată de Clay Mathematics Institute. Materialele din fizică nu au fost încă publicate integral. Ele urmează să fie analizate de un grup de specialiști coordonat de fizicianul David Gross, laureat al Premiului Nobel.

Cercetătorii vor verifica rezultatele generate de AI

OpenAI a ales o procedură diferită pentru prezentarea noilor rezultate, după controversele provocate de publicarea masivă a demonstrațiilor matematice la începutul lunii octombrie. Compania a format grupuri de cercetători care să examineze materialele, să identifice eventualele probleme și să explice rezultatele comunității academice.

OpenAI afirmă că nu va revendica merite academice pentru descoperirile generate de modelele sale. Specialiștii implicați vor primi recunoaștere pentru contribuțiile proprii la verificarea și explicarea lucrărilor. Demonstrațiile din matematică și informatică sunt deja disponibile public, în timp ce cercetătorii din fizică vor decide când și în ce formă vor prezenta materialele analizate.