Exponential Time Hypothesis (ETH)
Recommended reading: 【Modern Mathematics】 Table of Contents of Modern Mathematics
1. Overview
4. Conclusion
1. Overview
⑴ P vs. NP Problem
① Terminology
○ Deterministic algorithm: An algorithm that considers only one possible choice at each step of computation
○ Nondeterministic algorithm: An algorithm that considers two or more possible choices at each step of computation
○ Nondeterministic algorithms are theoretical concepts and cannot be directly implemented on actual computers.
○ They can simultaneously consider multiple possible paths at each step and are assumed to “luckily” select the correct path among them.
○ One can imagine an adventurer using clones of themselves to explore the optimal path at each step.
○ Even without the ability to create clones, the adventurer could still find the optimal path if someone provided a hint about which direction to take at every junction and the adventurer could verify that hint.
○ Therefore, a nondeterministic algorithm can be regarded as equivalent to a deterministic algorithm that verifies a given hint in polynomial time.
○ P problems = Problems that can be solved by deterministic algorithms in polynomial time
○ Here, the inability to solve a problem is interpreted as the impossibility of solving it with a deterministic algorithm in polynomial time.
○ NP problems = Problems that can be solved by nondeterministic algorithms in polynomial time = Problems whose solutions can be verified by deterministic algorithms in polynomial time
○ NP-hard: A problem to which every problem in NP is polynomial-time many-one reducible
○ It can be regarded as a problem that is at least as difficult as every problem in NP.
○ NP-complete: The class of problems that belong to NP and to which every problem in NP is polynomial-time many-one reducible
② Definition
○ Since deterministic algorithms $\subseteq$ nondeterministic algorithms (e.g., one correct choice and one random choice at each step), $P \subseteq NP$ holds.
○ The P vs. NP problem asks whether NP problems are identical to P problems or whether NP contains strictly more problems, and whether this relationship can be proved.
○ NP problems = (P problems) + (NP-complete problems) + (NP problems that are not NP-complete if $P \neq NP$)
Figure 1. P vs. NP Problem
③ Examples
○ Shortest path problem between two cities: A P problem. Solvable using Dijkstra’s algorithm, the Floyd algorithm, etc.
○ Greatest common divisor problem: A P problem. Solvable using the Euclidean algorithm
○ Sorting problem: A P problem. Solvable using bubble sort, quicksort, etc.
○ Prime factorization: It has not been proved whether it is NP-complete, not NP-complete, or whether such a classification is unprovable.
○ Traveling salesman problem (TSP): An NP-complete problem. Given multiple cities and the distances between them, the objective is to find the shortest route that visits every city exactly once and returns to the starting point.
○ Fragment orientation problem (FOP): NP-complete. A problem in bioinformatics that involves correctly determining the orientations of DNA fragments.
○ Super Mario Bros.: NP-hard
○ RNA structure prediction allowing pseudoknots or long-range constraints: NP-complete or NP-hard
○ Finding a subset that is as widely distributed and as informative as possible: NP-hard
○ Steiner tree problem: NP-hard
⑵ 3-SAT: A problem of determining whether there exists an assignment of Boolean variables (true or false) that satisfies all conditions in a logical formula.
① A 3-SAT formula is fundamentally composed of only three logical operations: OR, AND, and NOT: XOR can also be expressed as a combination of these operations.
② Every NP problem can be represented as a 3-SAT problem.
③ Example 1. For $F = (x_1 \lor x_2) \land (\neg x_1 \lor x_3)$, the formula is true when $(x_1, x_2, x_3) = (1, 0, 1)$. With $n$ variables, approximately $2^n$ assignments must be examined by exhaustive search.
⑶ ETH: The hypothesis that 3-SAT cannot be solved in $2^{o(n)}$ time complexity in the worst case.
① Example 1. $2^n$: Exhaustive search
② Example 2. $2^{0.5n}$: Faster, but still exponential time
③ Example 3. $2^{0.01n}$: Still compatible with ETH
④ Example 4. $2^{n/\sqrt{\log n}}$: Subexponential time, contradicting ETH
⑤ Example 5. $n^{10}$: Polynomial time. Would refute not only ETH but also $P \neq NP$.
⑥ On October 25, 2026, OpenAI (released earlier) and Anthropic (easier to understand and more efficient) independently refuted ETH using different approaches.
⑦ Even if the claims refuting ETH are correct, they do not prove $P = NP$: The time complexities of these algorithms remain much greater than polynomial time.
2. Anthropic’s Refutation 📃
⑴ Step 1. Consider #SAT, a problem harder than SAT.
① SAT: Does there exist at least one satisfying assignment?
② #SAT: Exactly how many satisfying assignments exist?
③ $[P]$: 1 if $P$ is true, and 0 if $P$ is false.
④ This idea is equivalent to Goldbach’s proof of the primality of the weak conjecture
⑵ Step 2. To represent #SAT, consider tensor contraction, which evaluates sums and products in a tensor network.
⑶ Step 3. Cost reduction using 3-bit blocks
① Eight-square identity (Degen–Graves–Cayley identity)
\[(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2\]○ Two-square identity: Corresponds to the complex numbers $\mathbb{C}$
○ Four-square identity: Corresponds to the quaternions $\mathbb{H}$
○ If both $m$ and $n$ are sums of the squares of four integers, then $mn$ can also be expressed as a sum of the squares of four integers.
○ Let $m = a_1^2 + a_2^2 + a_3^2 + a_4^2$ and $n = b_1^2 + b_2^2 + b_3^2 + b_4^2$.
\[mn = (a_1b_1 - a_2b_2 - a_3b_3 - a_4b_4)^2 + (a_1b_2 + a_2b_1 + a_3b_4 - a_4b_3)^2 + (a_1b_3 - a_2b_4 + a_3b_1 + a_4b_2)^2 + (a_1b_4 + a_2b_3 - a_3b_2 + a_4b_1)^2.\]○ This is because their product can be expressed as
○ This is used in the proof of Lagrange’s four-square theorem.
○ Eight-square identity: Corresponds to the octonions $\mathbb{O}$
○ Lagrange’s four-square theorem was proved in 1770, and Degen’s eight-square identity was discovered around 1818.
○ For arbitrary real numbers $a_i$ and $b_i$, there exist suitable values $c_i$ such that $(a_0^2 + \cdots + a_7^2)(b_0^2 + \cdots + b_7^2) = c_0^2 + \cdots + c_7^2$
○ Sixteen-square identity
○ Hurwitz’s theorem rules out the existence of a 16-dimensional real bilinear sum-of-squares identity analogous to the eight-square identity.
② Anthropic uses the octonion multiplication structure to establish the following identity for $x,y,u,v \in {0,1}^3$ and a certain function $\sigma$ that returns either $+1$ or $-1$.
○ $2[x=v][y=u] = [x \oplus y \oplus u \oplus v = 0] \cdot \left(\sigma(x,y)\sigma(v,u) + \sigma(x,u)\sigma(v,y)\right) = R+C$
○ Checking each of $[x=v]$ and $[y=u]$ requires 3 bits.
○ This can be understood as four 3-bit strings $x,y,u,v$ placed at the four corners, with two diagonal equality constraints $x=v$ and $y=u$.
○ $R$ is a term favorable for computation along the row direction, while $C$ is favorable for computation along the column direction: Their actual expressions are complicated, so they are represented in this simplified form.
Figure 2. Schematic illustration of a triangle consisting of four nodes
③ Cost reduction
○ Original cost: Computing $x=y$ and $u=v$ requires 6 bits.
○ Improved cost: Depending on the partitioning method, either 3 bits or 6 bits are required, resulting in an average of 4.5 bits, which is better than the original cost.
| Row-wise partition $([x,y],[u,v])$ | Column-wise partition $([x,u],[y,v])$ | |
|---|---|---|
| $R$ | 3 bits | 6 bits |
| $C$ | 6 bits | 3 bits |
Table 1. Connection cost of each term according to the partitioning direction
○ In other words, computational cost is reduced by using an identity that necessarily holds.
⑷ Step 4. Final refutation of ETH
① 4-1. Adding selection cost: By spending 1 additional bit to select either a row or a column, the exponential increase in the number of terms is controlled → A total of 5.5 bits is required.
\[T_A \approx 2^{t|\mathcal{R}|} \cdot 2^{e(4.5t|\mathcal{R}|+s_0)}\]○ ❌ Method A. Expand all $2^t$ terms: Although the connection cost of each term is smaller, exponentially many terms must be computed separately (ultimately requiring exponential time).
\[T_B \approx (t+1)^{|\mathcal{R}|} \cdot 2^{e(5.5t|\mathcal{R}|+s_0)}\]○ ✅ Method B. Group the terms into $A_0, \cdots, A_t$ and compute them together: Although the connection cost of each term increases by 1 bit, the number of external terms requiring recursive computation is greatly reduced.
\[\begin{aligned} A_0 &= R_1R_2R_3 \\[6pt] A_1 &= C_1R_2R_3 + R_1C_2R_3 + R_1R_2C_3 \\[6pt] A_2 &= C_1C_2R_3 + C_1R_2C_3 + R_1C_2C_3 \\[6pt] A_3 &= C_1C_2C_3 \end{aligned}\]○ e.g., with $t=3$,
○ The reason 3-bit blocks were chosen initially is that this is the first block size for which the reduction in connection cost from the eight-square identity exceeds the additional cost of selection information.
○ However, more sophisticated tensor-rank analysis may reveal cost reductions even for smaller blocks.
② 4-2. Recursive gain by a factor of $11/12$: The transformed problem is reconstructed as a tensor network of the same form, achieving an exponential improvement corresponding to a factor of $11/12$ in the exponent.
Figure 3. Recursive gain by a factor of $11/12$
\[\begin{aligned} K_0 &= 64, \qquad e_0 = 1 \\[8pt] K_\ell &= 9K_{\ell-1}^{16} \\[8pt] e_\ell &= \left(\frac{11}{12}+\frac{2}{K_{\ell-1}}\right)e_{\ell-1}+\frac{5}{K_{\ell-1}} \\[8pt] \therefore\ e_\ell &\le 1.12\left(\frac{11}{12}\right)^\ell \\[8pt] \therefore\ \forall \delta &> 0,\qquad T(\#3\mathrm{SAT}) \le O(2^{\delta n}) \end{aligned}\]③ 4-3. Actual algorithm implementation and completion of the refutation
⑷ Remarks
① All 3-SAT problems $\subseteq$ generalized tensor networks: In a tensor network, $W_a$ does not necessarily have to be a logical formula and may instead be an arbitrary integer-valued function.
② Any logical formula can be represented as a tensor network with equality connections, and the identity can be applied to locally restructure those connections.
③ Since the specific content of the logical formula remains encoded in the node functions, the applicability of the identity does not restrict the types of original logical formulas.
④ The critical point that must actually be verified is whether the tensor network can be rearranged into a rectangular structure suitable for the eight-square identity without causing an excessive increase in computational cost.
3. OpenAI’s Refutation 📃
⑴ Step 1. Convert 3-SAT into a problem of counting the number of satisfying assignments.
⑵ Step 2. Polynomial transformation.
⑶ Step 3. Separate groups using a small number of shared summary values: These summary values represent an exact conditional decomposition rather than an approximation.
⑷ Step 4. Recover the original number of satisfying assignments through interpolation.
4. Conclusion
⑴ Anthropic is ahead in terms of Lean formal verification: This is understandable given the exponent factor of $11/12$ in the proof above.
① OpenAI (Lean verification): $O\left(2^{\frac{n(\log\log n)^2}{\sqrt{\log n}}}\right)$
② OpenAI (paper): $O\left( 2^{\frac{n\log\log n}{\sqrt{\log n}}} \right)$
③ Anthropic (paper and Lean verification): $O\left( 2^{\min\left\lbrace\frac{m}{\sqrt{\log m}},\frac{n\log\log n}{\sqrt{\log n}}\right\rbrace} \right)$
⑵ The strongest upper bound on time complexity in OpenAI’s paper is also obtained through tensor-network computation in Appendix D, similarly to Anthropic’s approach.
⑶ Conclusion
① Although the number of possible variable assignments is $2^n$, the intrinsic degrees of freedom of 3-SAT itself may not be that large (e.g., due to the octonion multiplication structure), which seems to explain why the time complexity can be reduced below $2^n$.
② The fact that the number of clauses $m$ appears in the time complexity of Anthropic’s algorithm also supports this interpretation.
③ If the problem representation of 3-SAT, whose solutions can be verified in polynomial time (= NP), is much smaller than expected and can be described by a polynomial-time algorithm, then solutions could also be found in polynomial time (= P), thereby proving $P = NP$.
Posted: 2026.10.31 14:10