ETH is now a live research question, not just a background assumption
OpenAI and Anthropic say AI-generated work has produced subexponential algorithms relevant to the Exponential Time Hypothesis: OpenAI’s preprint targets fixed-width CNF problems, while Anthropic’s repository describes a deterministic subexponential-time algorithm for 3-SAT. OpenAI also released a Lean formalization.
This is not a P-versus-NP result, and neither claim is established consensus. Russell Impagliazzo, Ramamohan Paturi and Ryan Williams are organizing an independent examination; their involvement is explicitly not certification. The key review questions are whether the proofs are sound, whether the algorithms have the claimed scope, and whether they genuinely refute ETH.
If validated, which ETH-based lower bounds and complexity classifications would need to be revisited first? https://spaisee.com/article/ai-s-math-challenge-could-rewrite-how-computer-scientists-measure-diff
SPAISEE
npub1r3…pna4q
2026-10-28 10:05:00 UTC
Author Public Key
npub1r3usm7fjx33mnhrgejw6fg4glna706tkyzlfktgxgec2y2qzdmfqcpna4qSeen on
wss://relay.damus.ioPublished at
2026-10-28 10:05:00 UTCEvent JSON
{
"id": "e16149c56b9bdaf18c72fd7f4f7c61308eaffd7db52439ebb7ee94dd3fbb85e7",
"pubkey": "1c790df9323463b9dc68cc9da4a2a8fcfbe7e97620be9b2d064670a228026ed2",
"created_at": 1793181900,
"kind": 1,
"tags": [
[
"r",
"https://spaisee.com/article/ai-s-math-challenge-could-rewrite-how-computer-scientists-measure-diff?utm_source=nostr\u0026utm_medium=social"
]
],
"content": "ETH is now a live research question, not just a background assumption\n\nOpenAI and Anthropic say AI-generated work has produced subexponential algorithms relevant to the Exponential Time Hypothesis: OpenAI’s preprint targets fixed-width CNF problems, while Anthropic’s repository describes a deterministic subexponential-time algorithm for 3-SAT. OpenAI also released a Lean formalization.\n\nThis is not a P-versus-NP result, and neither claim is established consensus. Russell Impagliazzo, Ramamohan Paturi and Ryan Williams are organizing an independent examination; their involvement is explicitly not certification. The key review questions are whether the proofs are sound, whether the algorithms have the claimed scope, and whether they genuinely refute ETH.\n\nIf validated, which ETH-based lower bounds and complexity classifications would need to be revisited first? https://spaisee.com/article/ai-s-math-challenge-could-rewrite-how-computer-scientists-measure-diff",
"sig": "dcb9d24f55f1d9222dcd28fa655dd078fd0ef1fd29ab5d63469f7b23869d5adf72d813e2ad08e1559bd083dc30ac4f487956beb20225fa4feb7180b9fd136776"
}