VibeMathedMath problems solved with AI
Sign in

Williams's one-tape question: simulating one-tape time TT in O(T1/2−δ)O(T^{1/2-\delta}) space

A classical simulation (attributed to Hopcroft and Ullman) computes the outcome of a deterministic one-tape Turing machine running for TT steps in O(T)O(\sqrt T) space, with unrestricted simulation time. Williams (2025) proved that multitape time tt can be simulated in O(tlog⁡t)O(\sqrt{t\log t}) space using the Cook-Mertz tree-evaluation algorithm, and asked in Section 5 of his full version whether, for one-tape machines, the square-root exponent can be lowered by a fixed positive constant. Is there δ>0\delta>0 such that a one-tape machine running for TT steps can be simulated in O(T1/2−δ)O(T^{1/2-\delta}) space?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Computational complexity; time-space simulation
Posed by
R. Ryan Williams (Simulating Time with Square-Root Space, STOC 2025; question in Section 5 of the full version)
Year posed
2025
Years open
1y
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
20 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for a fixed deterministic machine with one writable tape and head (and finitely many read-only input heads), the finite-control and halting outcome by time TT can be computed in O(T2/5log⁡C(T+2))O(T^{2/5}\log^C(T+2)) work-space bits given the cap TT; without a supplied cap, a machine halting at time tt is simulated in O((t+2)2/5 polylog)O((t+2)^{2/5}\,\mathrm{polylog}) space. Hence O(T1/2−δ)O(T^{1/2-\delta}) for every δ<1/10\delta<1/10. Simulation time is unrestricted, the final tape is not materialized, no lower bound or optimality is claimed, and for several writable tapes only O(T polylog)O(\sqrt T\,\mathrm{polylog}) is given.

What the AI did

The release README says all results were produced by an unreleased internal OpenAI model using one fixed procedure, about three hours of ChatGPT Pro thinking compute per result on average. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region whose write-up was human-edited). The manuscript is authored 'OpenAI' and names no human author.

Verification

No independent mathematician has checked this yet. Checked here: the introduction and Theorem 1.1 were read against Williams's question as the paper reports it; Williams's full version was not opened. The family has no Lean formalization (lean/docs/137.md does not exist at the pinned commit). The model is one writable tape with one head plus a fixed number of read-only input heads, unit moves, a supplied binary time cap, and an accessor giving initial symbols in polylogarithmic space; the paper says the ordinary one-tape decision model is included. The bound carries polylogarithmic factors (no log-free 2/5 endpoint), the simulation is not time-efficient, and the multitape exponent is not improved.

Sources

Changelog1 change

Discussion