Scientific concept illustration of a path in a huge bifurcation search space for inspection

The cover is a concept of AI generation; the maze and light path are metaphors, not algorithmic structures, real experiments or performance results.

  • Interpretation date: 2026-10-27
  • Data deadline: 2026-10-27 20:31:22 (Beijing time, Asia/Shanghai)

On October 26, OpenAI announced that its internal model gave the rebuttal of the exponential time hypothesis (ETH) and disclosed the natural language manuscript and Lean formalized material. This is a major claim worthy of serious examination: it may change the judgment of computer science to "how difficult it is". However, public materials, machine verification and academic understanding are different links. The most valuable question today is what this claim has already provided and what work is left to the researchers. official announcement

To overthrow, what is the calculation boundary?

First imagine a set of switches: each switch can only be true or false, each rule requires at least one condition to meet at least one, and all rules must be established at the same time. 3-SAT asks whether there is a switch configuration that satisfies all the rules when each rule involves up to three text items. The text item here can be a variable or its negation.

ETH does not mean that all configurations must be tried one by one, but asserts that in terms of variable number, such problems cannot be generally reduced to the sub-index time in the worst case. The sub-index can be recorded as 2o(n)2^{o(n)}, which means that the proportion of the number of relative variables of the exponential part will become zero as the scale increases, and it needs to be included in the overhead of reading and processing input. Summary and introduction to the manuscript

This manuscript claims that the completed task is stronger: for a formula with fixed clause widths, the total number of configurations that meet the conditions is accurately calculated, and polynomial space is used. As long as the total number is greater than zero, you can answer whether there is a solution. Take the width of three and touch the core of ETH. Therefore, it is worth paying attention to the theoretical boundary that grows with scale, rather than a few more correct questions on a test set.

What ideas do the manuscript give and how to read the date?

In the manuscript’s overview, the algorithm expresses logical conditions as polynomials and uses them to compute an exact count. If the variables fell into independent groups, one could count within each group and combine the results. The difficulty lies in dependencies across groups. The authors seek to capture those dependencies with a few shared linear summaries and recover the total count using algebraic techniques such as interpolation. This sketch gives the intuition. The full proof must establish that the procedure works. Manuscript Section 2

The timeline also cannot be compressed into "discovery today". OpenAI says natural language rebuttals are produced in October 16, the next day to complete formalization; open PDF labeling Revised on October 17th, October 25th; the announcement date is October 26. The announcement does not give an exact time zone, and this article does not assert that it occurred in the past twenty-four hours. Announcement timeline

These materials also do not give information on the peer-reviewed entries that can be confirmed herein. They should be read as a public study manuscript and pending review.

The upper bound of Lean covered by the manuscript is not exactly the same as the manuscript

Lean is the proof assistant: write propositions and derivations as formal languages, and then check their logical dependencies. It provides a more specific object for the review than a smooth statement, but it still needs people to judge whether the formal proposition accurately expresses the original question.

The scope description of OpenAI clearly distinguishes two levels: Lean covers the exact count, time exponential time and polynomial space on the canonical code input; the manuscript on October 25 gives a tighter time upper bound. The two exponential terms differ by a double log factor, and the manuscript has a stronger boundary when the number of clauses is a fixed multiple of the number of variables. The best form of the manuscript cannot be directly marked as "all validated by Lean". Formal Scope Explanation

Even the looser upper bound in the scope note is subexponential, so this difference alone does not invalidate the proposed refutation of ETH. Reviewers still need to establish how encoding length enters the cost, how the machine model is defined, and whether the quantifiers require one algorithm to handle every admissible input. I checked the scope note and the publicly released theorem statement. I did not run the proof checker or verify the entire proof step by step.

Another proof that it cannot automatically act as a review report

As of the deadline, Anthropic's public repository also provides Claude's sub-index 3-SAT algorithm manuscript and formalized materials. Its explanation also emphasizes that the result is asymptotic conclusion, and clearly reminds that the machine checks the certificate, and does not automatically check whether the formal proposition is consistent with the paper description. This article reads the repository description, and has not yet completed the technical comparison of the two certificates. Anthropic raw material

This adds researchable material, but cannot simply be cumulatively "two independent verifications". Another team put forward the same kind of conclusions, and the first argument with external researchers successfully reviewed is two kinds of evidence. Whether they share key ideas and whether they have the same blind spots are still worth comparing.

Russell Impagliazzo, Ramamohan Paturi and Ryan Williams stated in the open letter that participating in the work should not be regarded as a certification of claims. They invite the community to examine the demonstration, interpretation methods, and research consequences, and also discuss how to recognize the labor of verification and simplification. Open Letter to Theoretical Computer Science Community

This letter provides a review position and is not a conclusion of the correctness that has been completed. No material sufficient to report "independent review has been completed" was found in this search.

What can scientific readers pay attention to now?

First, the sub-index may still grow faster than any polynomial, so this claim cannot be read as already resolved p and np. Second, the manuscript reminds itself: the general polynomial reduction may enlarge the scale of the variable, and all NP problems cannot be deduced from this to have a secondary index algorithm. The theoretical boundary does not give the acceleration ratio on the actual input. Manuscript page 2

Even if the rebuttal is established, the conditional theorem that was written as "if ETH is true, then an algorithm does not exist", it does not become an error proof. What is lost is a reason to directly regard the premise as a trusted basis; to design a faster algorithm for the goal problem, it is also necessary to control the direction and scale of the reduction. This is a logical distinction that should be maintained when reading existing papers.

The judgment of this article is: the importance of this event is enough to promote serious review, but the most worthy of the results at present is the simplified demonstration of reconstructable verification records, formal propositions and natural language propositions, and simplified arguments that can be understood and used by other researchers. When these materials appear, we can distinguish them more clearly: AI has proposed an important answer, or has it helped the academic community to establish a reliable new knowledge.

References

  1. OpenAI:Working with academic communities to build scientific understanding, 2026-10-26; read the text of the announcement.
  2. The Exponential Time Hypothesis is False, 2026-10-17, 2026-10-25 revision; read summary, introduction page 1–5 and method overview page 7–8, visual check page 2 The main theorem of the page master, the complete certificate has not been reviewed.
  3. OpenAI: Lean Formal Scope of ETH, the page is not marked with an independent publishing date; the full text has been read, and the linked proposition file has been checked, and the verification is not performed.
  4. Anthropic: A SubExponential Time Algorithm for 3-SAT, repository description, the page is not marked with an independent publishing date; the full text has been read, and the full paper has not been read or a running certificate.
  5. Impagliazzo、Paturi、Williams:Message to the TCS Community on ETH, the document is not marked with an independent date; the text is read through the export of public text, and the media has a link on October 26. The letter is a first-hand position material for reviewing organizers.

Apps by the author

In addition to writing tech blogs, I'm also doing some gadgets that make everyday life more organized. The following are the two apps I independently developed, which belong to the author's own works promotion, welcome to understand:

  • Daily Expense Journal: Record the daily income and expenditure, arrange the budget and savings goals, so that the whereabouts of each money is more clear. View on the App Store.
  • One Small Action: Choose a small action according to the current time and energy, record the feelings and discoveries after completion, and make it easier to start daily actions and reviews. View on the App Store.

Find more articles and projects on my website: zffjzz.top.