Discoveries / theoretical-computer-science

Source authenticated

The Sakoda-Sipser problem: exponential cost of simulating nondeterministic automata by two-way deterministic ones

For every $h\ge2$ , one-way liveness $\mathrm{OWL}_h$ has a nondeterministic automaton with $h+3$ states and no left moves, while every equivalent 2DFA with $s$ states satisfies $4(s+2)^2\ge2^{\lfloor(h-2)/31\rfloor}$ . Hence no polynomial $Cn^c$ bounds 1NFA-to-2DFA (and so 2NFA-to-2DFA) conversion uniformly over finite alphabets. The deterministic target is unrestricted (stay moves, partial rules, infinite rejecting runs). The companion gives the weaker-rate bound $\tfrac12 2^{\lfloor(n-4)/127\rfloor}$ for the same family. Not shown: any lower bound over a fixed alphabet (e.g. binary), any bound in transition-table size, or anything about L versus NL.

Exact FrontierDelta

Prior state unknown→disproved

Scope and record

Occurred: Sep 25, 2026

Delta type: SOURCE CLAIM

Assumptions: VibeMathed verification: lean-checked. Publication: announcement. AI contribution: ai-discovered. VibeMathed editorial classifications, scores, notes, relations, and dataset structure are CC BY 4.0. Source statements and linked content retain their own rights.

Canonical aliases: The Sakoda-Sipser problem: exponential cost of simulating nondeterministic automata by two-way deterministic ones · Sakoda-Sipser problem

Confidence: Not scored

Registry verification: lean checked · announcement · candidate

Open the source record ↗

Attribution

VibeMathed
registry · event recorded by

Unreleased internal OpenAI model
model · ai model contributor · OpenAI

Evidence vector

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Named evidence

VibeMathed record: The Sakoda-Sipser problem: exponential cost of simulating nondeterministic automata by two-way deterministic ones

specialist registry · passed

No independent mathematician has checked this yet. Checked here: Theorem 1.1 and Corollary 1.2 of the principal manuscript were read against the Sakoda-Sipser question. The witness is one-way liveness over the full relation alphabet, whose size grows with $h$ ; the claim rules out an alphabet-independent polynomial bound, which is the usual (Kapoutsis) formulation of the problem, and it does not give a bound over a fixed alphabet or any logarithmic-space separation, as the paper says. lean/formalization.yaml lists a main result for this manuscript (comparator OneWayLiveness, declaration OAI.OneWayLiveness.main_theorem, file OAI/Combinatorics/Automata/Main.lean). ComparatorChallenges/OneWayLiveness.lean was read here: it defines deterministic machines with partial transitions, stay moves and endmarkers, two acceptance conventions, and states the existence of the $(h+3)$ -state no-left-move recognizer and the bound $2^{\lfloor(h-2)/31\rfloor}\le4(s+2)^2$ (or $4(s+1)^2$ ) for every deterministic recognizer. This states the headline. Not rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice.

Source ↗

Sakoda and Sipser (STOC 1978)

specialist registry · pending

problem-record link supplied by the VibeMathed registry.

Source ↗

Comparator statement: OneWayLiveness.lean

lean artifact · pending

lean-proof link supplied by the VibeMathed registry.

Source ↗

Lean proof of the same-family determinization bound (explicit_family_main)

lean artifact · pending

lean-proof link supplied by the VibeMathed registry.

Source ↗

Companion: An exponential two-way deterministic state lower bound for one-way liveness

paper · pending

Primary source named by the VibeMathed record. Presence in this import is not an independent mathematical verification.

Source ↗

Polynomial complementation of two-way nondeterministic finite automata

witness · pending

paper link supplied by the VibeMathed registry.

Source ↗

Lean proof (OAI.OneWayLiveness.main_theorem)

lean artifact · pending

lean-proof link supplied by the VibeMathed registry.

Source ↗

Artifacts and verifiers

Comparator statement: OneWayLiveness.lean

lean artifact · pending

Artifact ↗

Lean proof of the same-family determinization bound (explicit_family_main)

lean artifact · pending

Artifact ↗

Lean proof (OAI.OneWayLiveness.main_theorem)

lean artifact · pending

Artifact ↗

Compute record

No linked compute attempts recorded.

Lineage and corrections

Sakoda and Sipser (STOC 1978) evidence for this event

This event attributed to Unreleased internal OpenAI model

Companion: An exponential two-way deterministic state lower bound for one-way liveness evidence for this event

VibeMathed record: The Sakoda-Sipser problem: exponential cost of simulating nondeterministic automata by two-way deterministic ones evidence for this event

The Sakoda-Sipser problem: exponential cost of simulating nondeterministic automata by two-way deterministic ones parent of this event

Lean proof (OAI.OneWayLiveness.main_theorem) evidence for this event

Lean proof of the same-family determinization bound (explicit_family_main) evidence for this event

Polynomial complementation of two-way nondeterministic finite automata evidence for this event

Comparator statement: OneWayLiveness.lean evidence for this event

Act on this frontier

Verify, challenge, or extend the result.

Help verify Open canonical problem Explore evidence graph