OpenAI models disprove exponential time hypothesis in computer science
OpenAI announced its internal models disproved the exponential time hypothesis, a core assumption in computational complexity theory. Experts describe the result as potentially one of the biggest breakthroughs in decades if it survives peer review.
OpenAI announced that its internal models disproved the exponential time hypothesis (ETH), a foundational assumption in computational complexity theory related to the P versus NP problem. ETH posited that adding variables to the 3SAT algorithm necessarily increases computation time exponentially. Fields medalist Timothy Gowers called the result surprising and consequential, while A16z’s Martin Casato described it as stunning. Mathematician Konsti Woland stated that if the result survives peer review, it could be one of the biggest computer science breakthroughs in decades. OpenAI’s Greg Brockman noted that while ETH is false, P still probably does not equal NP.
The company also proved a local smoothing conjecture in mathematics and made progress on an existence proof for interacting quantum field theories in physics, working with Nobel laureate David Gross. OpenAI partnered with expert scientists for verification, releasing the mathematics result in full while keeping the physics result private as it remains incomplete. The disproof of ETH could have significant implications for cryptographic algorithms and computational efficiency, marking a notable instance of AI models contributing to fundamental theoretical research.