OpenAI has shared the prompt that led to the ETH refutation and agreed to release it publicly. Here is the prompt.
Research an unconditional refutation of the deterministic Strong Exponential Time Hypothesis (SETH). Seek a new, rigorous mathematical result; do not assume a refutation exists or present an incomplete argument as a proof.
The precise target is to establish
there exists epsilon in (0,1) such that, for every fixed integer k >= 3,
there exist a deterministic algorithm A_k and finite constants C_k > 0,
c_k >= 0 such that, for every k-CNF formula F,
A_k(F) correctly decides whether F is satisfiable, and
T_{A_k}(F) <= C_k (L(F)+1)^{c_k} 2^{(1-epsilon)n(F)}.
Here k-CNF means that every clause has at most k literals; n(F) is the number of variables, L(F) is the bit length of the input encoding, and T is total worst-case running time in a standard deterministic computation model. The same positive epsilon must work for all k. The algorithm, multiplicative constant, and polynomial degree may depend on k: a polynomial degree independent of k is not required. Each A_k must be a finite algorithm correct for all input lengths, without input-length-dependent advice. The target concerns every fixed k, not a time guarantee uniform over k growing with n.
Equivalently, if s_k is the infimum of achievable deterministic exponential exponents for k-CNF-SAT, with polynomial input-length factors suppressed, the goal is to prove lim_{k->infinity} s_k < 1. A rigorous alternative unconditional argument proving this equivalent statement is acceptable; establish the equivalence and any reductions needed rather than merely asserting a connection.
Develop and critically test promising mathematical approaches. For a claimed algorithmic refutation, give the algorithm, prove termination and correctness on every input (both satisfiable and unsatisfiable), and derive the stated running-time bound. Exhibit an epsilon with a proved positive lower bound independent of k. Account for all input reading, preprocessing, branching, sparsification, auxiliary constructions, subroutine calls, and any derandomization. Make parameter dependencies and reduction blowups explicit, including bit costs where relevant. If a restricted class is used as an intermediate step, prove that the reduction from arbitrary k-CNF instances preserves a positive uniform exponential saving.
Audit the quantifiers carefully. Improvements for only finitely many widths, savings epsilon_k tending to zero with k, subconstant savings in the exponent, average-case or promised-input algorithms, unsupported oracle steps, and randomized algorithms without a valid deterministic conversion do not establish this target. A conditional result must not be labeled an unconditional refutation.
End with the strongest result actually justified. If the target is proved, provide a complete theorem and proof. Otherwise state plainly that no refutation was obtained, distinguish proved lemmas from conjectures and failed approaches, and identify the precise remaining mathematical obstacle. Useful rigorous partial progress is preferable to a fabricated solution.
Definition references: Impagliazzo and Paturi, “Exact Complexity and Satisfiability” (IPEC 2013), p. 3, defines SETH through lim s_k = 1:
https://cseweb.ucsd.edu/~
Cygan et al., “On Problems as Hard as CNF-SAT,” discusses the equivalent fixed-width quantifier structure but explicitly uses bounded-error randomized algorithms; keep that convention distinct from this deterministic target:
