OpenAI and Anthropic claim AI-generated algorithms refute the Exponential Time Hypothesis; early checks find no cryptographic breaks
OpenAI released solutions to three long-standing math problems, including a claimed refutation of the Exponential Time Hypothesis (ETH), a core assumption in computational complexity. Hours later, Anthropic published its own refutation of ETH. Both labs claim their models found sub-exponential-time algorithms for a class of hard logic puzzles, which would weaken the evidence that P ≠ NP. MIT professor Ryan Williams, who is helping organize the computer science community's response, said OpenAI science lead Dan Roberts told him the lab had checked and was reasonably confident the result implies no breaks in current cryptographic systems. The claims have not yet been independently validated.
Detalhes técnicos
- ETH holds that algorithms need exponentially more time as the number of variables grows in a specific class of hard logic puzzles. It underpins much of the evidence that P ≠ NP.
- Williams said an improved algorithm could in principle imply that systems relying on certain key sizes are broken. OpenAI reportedly checked this and found no implied breaks. This is a vendor assurance, not independent verification.
- Williams described the proof as having routine parts and two or three "alien-looking" parts, and doubts OpenAI's algorithm is the best possible.
- Anthropic mathematician Levent Alpöge suggested OpenAI's solutions drew on pre-existing work.
Remediação
- No defensive action is required at this time. Cryptography teams should monitor the community review. Williams, Russell Impagliazzo and Ramamohan Paturi issued an open letter seeking feedback, and a conference on the results is planned.
Linha do tempo
-
OpenAI and Anthropic claim AI-generated algorithms refute the Exponential Time Hypothesis; early checks find no cryptographic breaks
ler a análise desta fonte ocultar
OpenAI released solutions to three long-standing math problems, including a claimed refutation of the Exponential Time Hypothesis (ETH), a core assumption in computational complexity. Hours later, Anthropic published its own refutation of ETH. Both labs claim their models found sub-exponential-time algorithms for a class of hard logic puzzles, which would weaken the evidence that P ≠ NP. MIT professor Ryan Williams, who is helping organize the computer science community's response, said OpenAI science lead Dan Roberts told him the lab had checked and was reasonably confident the result implies no breaks in current cryptographic systems. The claims have not yet been independently validated.
Technical Details
- ETH holds that algorithms need exponentially more time as the number of variables grows in a specific class of hard logic puzzles. It underpins much of the evidence that P ≠ NP.
- Williams said an improved algorithm could in principle imply that systems relying on certain key sizes are broken. OpenAI reportedly checked this and found no implied breaks. This is a vendor assurance, not independent verification.
- Williams described the proof as having routine parts and two or three "alien-looking" parts, and doubts OpenAI's algorithm is the best possible.
- Anthropic mathematician Levent Alpöge suggested OpenAI's solutions drew on pre-existing work.
Remediation
- No defensive action is required at this time. Cryptography teams should monitor the community review. Williams, Russell Impagliazzo and Ramamohan Paturi issued an open letter seeking feedback, and a conference on the results is planned.