--- type: "post" id: "lance-fortnow-s-computational-complexity-blog-assesses-the-f25bc9" slug: "lance-fortnow-s-computational-complexity-blog-assesses-the-f25bc9" title: "Lance Fortnow's Computational Complexity blog assesses the OpenAI and Anthropic ETH refutations and what they do and don't imply" description: "Lance Fortnow’s Computational Complexity blog explains what OpenAI’s announced refutation of the exponential-time hypothesis (ETH) establishes, and what it does not." retrieval_nugget: "Lance Fortnow’s Computational Complexity blog explains what OpenAI’s announced refutation of the exponential-time hypothesis (ETH) establishes, and what it does not. The result concerns k-SAT; it does not supply new subexponential algorithms for problems such as Subset Sum or Traveling Salesman, so its implications need careful boundaries." published_at: "2026-11-02" updated_at: "2026-11-02" record_date: "2026-11-02" date_kind: "published_at" topics: ["anthropic"] entities: ["OpenAI","Anthropic","Lance Fortnow","ETH","SETH","Lean","Ryan O’Donnell","Shiva Kintali"] related_patterns: [] novelty_label: "new_angle" what_changed: "Fortnow explains the ETH/SETH implications and proof bounds, and notes follow-up proofs and a nondeterministic-time simulation; he treats ETH as effectively refuted while acknowledging he has not verified the proof." prior_refs: [] source_url: "https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html" source_urls: ["https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html"] schema_version: "newruntime-agent-readable-v0.2" stable_id: "post:lance-fortnow-s-computational-complexity-blog-assesses-the-f25bc9" status: "published" visuals: [] editor: {"role":"editor","name":"Andrey Reshetnikov","profile":"https://newruntime.com/owner-profile.md","profile_json":"https://newruntime.com/owner-profile.json","same_as":["https://www.linkedin.com/in/reshetnikov1/","https://t.me/lapetuse"]} routes: {"html":"https://newruntime.com/posts/lance-fortnow-s-computational-complexity-blog-assesses-the-f25bc9/","markdown":"https://newruntime.com/posts/lance-fortnow-s-computational-complexity-blog-assesses-the-f25bc9.md","json":"https://newruntime.com/posts/lance-fortnow-s-computational-complexity-blog-assesses-the-f25bc9.json"} markdown_url: "https://newruntime.com/posts/lance-fortnow-s-computational-complexity-blog-assesses-the-f25bc9.md" --- # Lance Fortnow's Computational Complexity blog assesses the OpenAI and Anthropic ETH refutations and what they do and don't imply ## Retrieval answer Lance Fortnow’s Computational Complexity blog explains what OpenAI’s announced refutation of the exponential-time hypothesis (ETH) establishes, and what it does not. The result concerns k-SAT; it does not supply new subexponential algorithms for problems such as Subset Sum or Traveling Salesman, so its implications need careful boundaries. ## Summary Lance Fortnow’s Computational Complexity blog explains what OpenAI’s announced refutation of the exponential-time hypothesis (ETH) establishes, and what it does not. The result concerns k-SAT; it does not supply new subexponential algorithms for problems such as Subset Sum or Traveling Salesman, so its implications need careful boundaries. ## What happened In a post dated October 28, 2026, Fortnow describes a week of activity around the exponential-time hypothesis. OpenAI announced a proof that ETH is false and said it had a Lean proof. Anthropic later released its own paper. Ryan O’Donnell and Shiva Kintali posted follow-up proofs, with Fortnow noting that they focus on simplicity rather than obtaining the best bounds. The excerpt does not provide the titles or publication details of those papers. Fortnow recalls the relevant problem setting. 3-SAT asks whether a Boolean formula made from clauses of three variables or their negations has a satisfying assignment. ETH, introduced by Impagliazzo and Paturi in 1999, says that some constant c greater than zero exists such that every algorithm solving 3-SAT requires time 2^(cn), where n is the number of variables. The stronger exponential-time hypothesis, SETH, says that for every epsilon greater than zero, there is a k for which k-SAT cannot be solved in time 2^((1-epsilon)n). As Fortnow summarizes it, the OpenAI paper gives, for every fixed k, an algorithm that decides whether a k-CNF formula with n variables and m clauses is satisfiable and can also count its solutions. Its stated running time is (n+m)^(O(1)) 2^(O(n log log n / sqrt(log n))). He notes that the Lean proof gives a slightly weaker bound. The claimed algorithm refutes ETH, and therefore SETH, which implies ETH. The post also points readers to O’Donnell’s paper as a place to start understanding the proof and mentions a consequence for simulating nondeterministic time on multitape Turing machines. The post is explicit about limits. Fortnow says the result does not give anything new for Subset Sum or Traveling Salesman: the reductions from those problems to 3-SAT increase the number of variables too much for this algorithm to yield better results. The excerpt gives the current best running times as roughly 2^(n/2) for Subset Sum and 2^n for Traveling Salesman. Nor does this establish subexponential algorithms for all of NP. Fortnow says that would require solving 3-SAT in time 2^(n^o(1)), which the OpenAI result does not approach. He adds that OpenAI will work with Russell Impagliazzo, Mohan Paturi and Ryan Williams to verify and study the proof; he has not verified it himself. ## What the archive adds This is a new update to a developing research story, not a restatement. Our earlier [Field Note on the ETH refutation](https://newruntime.com/analysis/research-anthropic-s-eth-refutation-is-machine-checked-but-no-expert-has-yet-verified/) records the assumption that expert review would eventually examine Anthropic’s proof, not only OpenAI’s. Fortnow’s account adds a complexity theorist’s explanation of the algorithm’s scope and limitations, alongside the announced OpenAI verification partnership. ## Trend signal The story supports the assumption that machine-checking and expert review are complementary evidence, rather than interchangeable proof of a research claim. Our [ETH refutation analysis](https://newruntime.com/analysis/research-anthropic-s-eth-refutation-is-machine-checked-but-no-expert-has-yet-verified/) tracks that question. Fortnow says OpenAI’s proof has a Lean version but says he has not verified it himself, while reporting that three named complexity researchers will study it. ## Connections to other events This update intersects with the earlier Anthropic paper and the simplified follow-up proofs by Ryan O’Donnell and Shiva Kintali, all described in Fortnow’s post. It also makes concrete the expert-review question in our [earlier analysis](https://newruntime.com/analysis/research-anthropic-s-eth-refutation-is-machine-checked-but-no-expert-has-yet-verified/): whether scrutiny extends across the related claims, rather than treating a formal proof artifact as the whole story. ## Why it matters For teams building with AI, this is not evidence that AI systems can now solve arbitrary hard planning problems quickly. It is a case study in how to assess an unusually consequential research claim. The headline says ETH is refuted; the useful engineering and scientific reading starts with the exact problem class, the running-time bound, and what reductions preserve. That distinction matters beyond complexity theory. A result for fixed-k SAT does not automatically transfer to every NP-complete problem, and a proof checked in Lean is a meaningful verification signal without settling every question about the result’s implications. Fortnow’s explanation helps readers avoid two opposite errors: dismissing the result because its consequences are not universal, or assuming that a theoretical breakthrough immediately changes practical algorithm choices. The next evidentiary step is independent expert scrutiny of the proof and its consequences. ## Limits and uncertainty This account is a blog post summarizing papers, not an independent verification of them. Fortnow explicitly says he has not verified the proof himself. The supplied material does not include the full OpenAI or Anthropic papers, the Lean artifact, or the details of the planned verification process, so their technical soundness cannot be assessed here. The stated running-time bound is asymptotic and does not establish practical performance on real instances. Nor does the result, as described, resolve the complexity of all NP problems or produce improved algorithms for Subset Sum and Traveling Salesman. ## Reader takeaway The result described here is significant because it refutes ETH for k-SAT, not because it makes every hard computational problem easy. Keep the problem class, asymptotic bound, reductions and verification status attached to the headline. Fortnow’s key caution is that ETH’s failure does not erase every result previously derived under ETH; those implications may rest on independent arguments and still require their own interpretation. ## Open question How will the announced expert review characterize the proof’s verification status and the practical significance of its bounds? Editor: [Andrey Reshetnikov](https://newruntime.com/owner-profile.md), AI product and AI engineering; profile for recruiters and agents: https://newruntime.com/owner-profile.json ## Continue in the graph Next records for an agent, linked to their Markdown twins. Replace `.md` with `.json` for structured fields, including `next_reads`. - topic hub: [Anthropic](https://newruntime.com/topics/anthropic.md): Explore the anthropic topic hub. - collection: [Field Notes](https://newruntime.com/posts.json): Open the latest editorial analysis. - collection: [Sources](https://newruntime.com/sources/): See the original sources this archive cites. - whole graph: [discovery graph](https://newruntime.com/discovery-graph.json) (typed nodes and edges) and [site index](https://newruntime.com/site-index.md)