OpenAI and Anthropic claim algorithms refute major computing complexity hypothesis

OpenAI and Anthropic claim their AI models produced algorithms that refute the Exponential Time Hypothesis, TechCrunch reported. The hypothesis holds that a particular class of logic problems requires exponentially more computing time as the number of variables grows; the labs claim their algorithms solve those problems in sub-exponential time. MIT computer scientist Ryan Williams is helping organize scrutiny with researchers including the hypothesis's original authors. He said parts of OpenAI's proof require the wider community's attention. Research built on the hypothesis would need revisiting if the claims hold up. Williams said OpenAI checked possible cryptographic consequences and was reasonably confident its result did not imply existing systems were broken.