Many people saw that OpenAI just used AI to disprove the Exponential Time Hypothesis (ETH). So does that mean @OpenAI is about to destroy the existing social order? Does it mean that if we just have enough tokens, we can solve any problem in the future? Today’s hot OpenAI paper on the ETH solution has led a lot of people to believe two things: 1. The P vs NP problem has been solved, so the era of AI solving everything has arrived. 2. The Great Acceleration is here, every problem can now be computed. I spent an hour carefully reading the paper and found it’s actually not as exaggerated as most people think. Here’s a simple explanation of the key concepts: --- First, what is the P vs NP problem? When I started learning algorithms around age 16, I was obsessed with P vs NP. Why? Bc if it were solved, it would mean that with enough computing power, you could instantly get the answer to almost anything in the universe. Simply put, the core question is: “Are problems that can be verified in polynomial time equal to problems that can be solved in polynomial time?” What is polynomial time? Any algorithm can basically be reduced to forms like O(n), O(n^2), etc. Here n is the size of the input, and the big-O notation tells you roughly how long the computation will take as n grows. If P = NP, then essentially everything becomes computable. Humanity would have obtained the “cheat code” of the universe. From that point on, with enough tokens: - We could instantly reverse-engineer drugs that cure any disease. - AI could exhaustively search and find the perfect rocket launch trajectory in seconds. - Logistics optimization, AI training, weather forecasting… all of it could be solved in seconds by throwing more tokens at it. --- However, if the mainstream scientific view is correct and P ≠ NP, then many problems cannot be solved in polynomial time; they require exponential time. What is exponential time? Exponential time means the complexity is not O(n^c), but something like O(2^n). Every time n increases by 1, the amount of computation roughly doubles. Problems that require exponential time and cannot be reduced to polynomial time mean that no matter how many tokens you burn, you may never get the answer in any practical timeframe. In reality, protein folding for new drug discovery and the RSA encryption that protects your online banking are both classic exponential-time hard problems. Even if you burned all the computing power on Earth, you still wouldn’t get the answer before the solar system dies. If P = NP were true, exponential-time problems could be converted into polynomial-time ones through algorithmic engineering. Humans could create almost anything with AI, or destroy and break almost anything. --- So what’s the connection between this ETH result and P vs NP? A lot of people are saying: “ETH showed that 3-SAT (an exponential-time problem) has a better solution, so P vs NP is basically solved.” That’s not actually the case. Even if this particular exponential-time case (3-SAT) has been refuted under ETH, P vs NP remains unsolved. Why? Bc what happened here is that O(2^n) exponential time was improved to 2^{O(n/sqrt(log n))} — which is sub-exponential time, but still not polynomial time. As n gets larger, the complexity still explodes, just not quite as fast as pure exponential. In essence, AI shortened the time from “hundreds of billions of years” to something like “hundreds of millions of years.” That said, this is still worth paying attention to. AI has already come up with a way to reduce exponential time that humans hadn’t thought of before. As AI continues to advance, many classic hard problems that we had basically written off as “impossible to compute faster” are now open questions again. In other words, the assumption that “exponential time cannot become polynomial time” still has a chance of being overturned — just not yet. It’s similar to what Vitalik Buterin @VitalikButerin (the other “ETH”) said recently about the possibility of AI breaking ECDSA: > In any mathematical structure, “there exists a hidden 4th solution” is more likely than “there are exactly 3 solutions.”