math/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf at main · openai/math
github.com
Contribute to openai/math development by creating an account on GitHub.

OpenAI (and allegedly anthropic?) had models prove that the ETH is false. The proof is short, relatively easy to read, and the construction is not esoteric: I believe this is very likely correct.

The Exponential Time Hypothesis (ETH) is the conjecture that it takes exponential time to solve 3-SAT. 3-SAT (short for satisfiability) asks how long it takes a computer to find a solution to a boolean equation of the form (A or not B or C) and (not A or D or E) and (F or not C or D) … where there are $n$ boolean variables and $m$ clauses. It was believed that this should take, essentially, $(4/3)^n$ time for the fastest algorithm (roughly equivalent to brute forcing all possible boolean values for the variables).

But it is possible to do much better. They give a divide-and-conquor algorithm based on polynomial interpolation that runs in roughly $2^{n/log(n)}$ time (which grows slower than $b^n$ for any $b>1$). This implementation isn’t useful for SAT instances smaller than the universe, so internet security is fine. But often these algorithms get improved.

This is shocking; it was pretty widely believed that ETH was the reason that P!=NP. It has fallen; will any other barrier survive?

(I acknowledge that folks do not like AI solving open questions in math, there are many reasons this is bad for the community. This problem is not like most problems; this is closer to curing cancer than painting a picture. ETH has consequences, and if this approach has a shred of improvement over existing SAT solvers (which it does, or a human would have published this earlier), it will save energy, lives, and resources for humanity for awhile to come.)

  • eleijeep@piefed.socialEnglish
    51·
    9 days ago

    They give a divide-and-conquor algorithm based on polynomial interpolation that runs in roughly $2^{n/log(n)}$ time
    …
    This is shocking; it was pretty widely believed that ETH was the reason that P!=NP. It has fallen; will any other barrier survive?

    I’m not a mathematician, but explain this to me please:

    P means “polynomial-time”, NP means “non-polynomial time.” How exactly are you suggesting that an O(2^(n/log n)) algorithm (if correct) has any bearing on P=NP? 3SAT is still in NP even with this minor improvement.

    • dfyx@piefed.socialEnglish
      14·
      9 days ago

      NP doesn’t mean “non-polynomial time”, it means “nondeterministic polynomial time”, i.e. for a turing machine that is allowed to make random decisions, at least one of the random paths solves the problem in polynomial time. We have known for a long time that we can simulate such a machine in exponential time (essentially by trying all possible paths sequentially) and that there is a class of problems (NP-complete) where if we find a faster solution for one of them, we can derive an equally fast (in terms of O) solution for all of them. 3SAT is one of those NP-complete problems.

      While reducing the complexity from O(c^n) to O(c^(n/log n)) is still far from O(n^c), it shows that what we assumed might be a hard limit if P!=NP isn’t true. There might still be a limit that has some term of n as its exponent or it might not. What this finding suggests is that at least the term is better than just n, meaning we are at least getting closer to a polynomial solution, even if it’s baby steps. So far, there is no practical consequence of this but it gives us a direction for possible further attempts.

      For these kinds of problems, finding a solution is often about slowly finding tighter and tighter upper and lower bounds, not about hitting the truth right away and we hadn’t found a new upper bound for NP-complete problems basically since they have been defined.

      Edit/Disclaimer: this is based on what I remember from University over a decade ago and a quick Wikipedia search. I might have gotten a few details wrong.

    • Artisian@lemmy.worldOPEnglish
      11·
      8 days ago

      A historical note that might help: P means poly-time; NP doesn’t mean anything as an acronym, we don’t have the story of how it was chosen. They just picked something. NP does not mean ‘all non-poly’ algorithms, it is much more restrictive, and there are many problems not in NP (for example, the halting problem is not in NP. Neither is listing out all solutions to a 3-sat problem, because often writing them all down takes too long).

      What problems are in NP? These are problems whose solutions can be verified by a polynomial time checker. I can check if you have a solution to 3-SAT by taking a proposed answer, and checking that each clause (A or B or not C) is satisfied. This check is fast.

      It was widely believed (ETH) that NP-complete problems like 3-SAT were very far from P problems. ETH was suspected because checking an answer and finding an answer seem like really different processes, and so being able to check quickly shouldn’t help you find quickly whatsoever. This was wrong, and there’s no principled argument for what gap there should be between the two. P=NP is the most extreme case. I’m saying that we had a long standing and plausible gap between P and NP; and that gap just shrunk.

  • Minty@aussie.zone
    1·
    9 days ago

    Its honestly demoralising to see AI generate these big results, just from the perspective of a sort of death of the human component in maths, or human driven. Im not interested in doing maths research (im not good enough at it), but I imagine it must be depressing for a young aspiring mathematician see AI automating the thing they love, which is creatively problem solving and understanding.

    If this continous to the point where most proofs are basically done by AI, I think it makes the story of it all will be… bland. Like with the navier stokes results. The story isnt how buckworth spent his life on this one problem and then finally solved it… its how open ai spent millions on an AI generated proof. Even worse here, is open ai may have stolen his ideas.

    Anyway this just the opinion from someone who just enjoys solving the odd maths problems.

    • Artisian@lemmy.worldOPEnglish
      1·
      3 days ago

      Speaking personally, this was the first result that really cemented that I love math. Not people solving math, not the hero worship, and not the glory of it being me that solves it. The constructions and arguments and getting to understand it for myself are enough for me.

      The age of heroes was cool - now it is time for the age of oracles.

      • Minty@aussie.zone
        1·
        3 days ago

        An end of the age of heroes is something to lament, even if on a technical level AI could out perform humans on mathematical proofs. The death of human endavour on mathematical knowledge is a depressing thing.

        Theres also the issue of potential human understandability of the proofs. If the output is 1B lines of lean code, theres no human alive that can understand it, we will only know its true because it passes lean.

        Im not argueing against the use of AI on a technical level, but just saying its still depressing seeing it automated.

        • Artisian@lemmy.worldOPEnglish
          1·
          3 days ago

          I’m presently optimistic that there will still be mathematicians studying what’s true in maths; we’ll just be more like physicists or biologists. Reality is out there, doing physics regardless of if we understand it. We still want people to understand it, if only so we can make explosives. Much the same with mathematics, at least until we trust our new AI overlords entirely.