OpenAI preprint, September 2026 · §4. An exponential bound for order-reversing images · §4.2
§4.2 (setting): the target bound D(h):The target bound
,
exponential in
,
satisfies
for every
The exponential target bound and its doubling step.
Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its
declaration both in Lean and in words.
The Setting
One part of the exponential state lower bound for complementing two-way nondeterministic finite automata aims at an explicit target: a power of two in a natural number , exponential in . The question for this item is how far has to move for to double.
The Target Bound
The target bound of a natural number is the power of two (1)✦
The Claim
Theorem 1. Let be a natural number with .Then (2)✦
In the paper, the result reads: with , the target bound is for .
What Is Checked
The claim is stated over the target bound of (1), at every natural number .