Unbounded error counting time space alternative

Choose rational $0<\eta <{\eta }_1<\min (\epsilon ,1)$ and $a>\max (d,1)$. Suppose $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ has the stated time/space decider. For a language in ${\mathrm{L}\mathrm{C}\mathrm{H}}_{P,1}$, [F3] produces a formula of length $N=O(n{\log }^{k}n)$. Its source decider work extent is eventually below a known power-of-two bound $M=O(n^{1-{\eta }_1})$, because ${\eta }_1<\epsilon$ absorbs fixed constants and polylogs in $N$. In the basis profile use [F6] to simulate both ordinary reads and native basis queries on this generated formula in time $O((n+N+N^d+1)\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)$ and space $O(M+\log n)$. In the sequential profile [F3]'s ordered source-constant block, or a logarithmic virtual-input-position counter, gives at most the same overhead for each local input move without changing work records. The strict margins $a>\max (d,1)$ and $\eta <{\eta }_1$ bound these resources by $O(n^a)$ and $O(n^{1-\eta })$. Hence ${\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n)\subseteq {\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{S}\mathrm{P}}_P(n^a,n^{1-\eta })$.

Choose rational $1<b<B$ with $B(1-\eta )<1$, put $\beta =1-B(1-\eta )>0$, and choose rational $A>Ba$. For any ${\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n^b)$ language, its self-delimited padded version at length $m=\mathrm{\Theta }(n^B)$ has a linear-time decider. In the basis profile apply [F5] to the original fixed decider, then translate its short indices to the original-input portion of the actual padded word; the cost $n^b\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n$ fits $O(m)$ because $b<B$. Sequential simulation is no slower. Apply step 1.1 to that padded language. On the original word, its resulting time/space decider sees a generated input of length $m$. For the basis profile [F6] simulates this virtual padded input with a known work bound $M=O(m^{1-\eta })$ rounded to a power of two; its delimiter and zero bits have polylogarithmic-time/logspace generators. Time is $O(n^{Ba}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)\subseteq O(n^A)$ and work extent $O(m^{1-\eta }+\log n)=O(n^{1-\beta })$. The sequential virtual-input simulation has the same bounds. Thus ${\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n^b)\subseteq {\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{S}\mathrm{P}}_P(n^A,n^{1-\beta })\subseteq {\mathrm{L}\mathrm{C}\mathrm{H}}_{P,\tau }$ by [F2] for a fixed finite $\tau$. Increase $\tau$ to at least two if necessary.

Choose rational constants $1<c<\rho <\delta <b^{1\mathrm{/}(\tau -1)}$ and suppose $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ has a fixed ${\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n^c)$ decider. Let the reduction in [F3] map an $n$-bit input to a formula $y=R(x)$ of length $N=O(n{\log }^k(n+2))$ for some fixed $k$, with the stated direct bit generator. If $P=\mathrm{s}\mathrm{e}\mathrm{q}$, supply this formula on demand using [F3]'s sequential streaming guarantee; the decider then takes $O(N^c\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)=O(n^c\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)$ time. If $P=\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}$, the bit generator alone does not justify composition with a time-only decider that can issue long block queries. Choose a constructible clock $T=\lceil K_0(N+2{)}^c\rceil \ge N$ and apply [F5] to the decider's fixed explicit code. The resulting exact index-only interpreter has time and physical work-access extent bounded by a constructible $T^{\mathrm{\prime }}=O(N^c\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}N)$. Choose a power-of-two majorant $M_n=2^{\lceil K_1{\log }_2(n+2)\rceil }$ with fixed $K_1$ large enough that $T^{\mathrm{\prime }}\le M_n\le (n+2{)}^{K_1+1}$. The normalized index-only interpreter is a special case of the basis machine's head-access operations, with no native block query left; apply [F6] to its run on the generated formula $R(x)$. The formula length, bit generator, clock and address majorant satisfy [F6]'s hypotheses, so the exact simulation takes $O((n+T^{\mathrm{\prime }}+1){\log }^{O(1)}(n+2))=O(n^c{\log }^{O(1)}n)$ time. Thus in either profile ${\mathrm{L}\mathrm{C}\mathrm{H}}_{P,2}\subseteq {\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n^{\rho })$, with the strict exponent margin absorbing the reduction, normalization and generated-input overheads.

We prove the stronger induction assertion that for every $j\ge 2$ there is a rational $e_j^{\mathrm{\prime }}<{\delta }^{j-1}$ with ${\mathrm{L}\mathrm{C}\mathrm{H}}_{P,j}\subseteq {\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n^{e_j^{\mathrm{\prime }}})$. The base is $e_2^{\mathrm{\prime }}=\rho$. For the induction step, set $e={\delta }^{j-1}$ and take any $B\in {\mathrm{L}\mathrm{C}\mathrm{H}}_{P,j}$ with the resulting decider of time $O(\mathrm{\mid }q{\mathrm{\mid }}^{e_j^{\mathrm{\prime }}})$, where $e_j^{\mathrm{\prime }}<e$ and $e_j^{\mathrm{\prime }}>1$. Encode each padded query self-delimited, with its original query $q$ in a designated prefix and a zero suffix, to a length $m=\mathrm{\Theta }((\mathrm{\mid }q\mathrm{\mid }+2{)}^e)$. This padded language is in ${\mathrm{L}\mathrm{C}\mathrm{H}}_{P,1}$: verify its format in $O(m)$ time and run the $B$ decider on the logical input $q$. For $P=\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}$, first apply [F5] to the fixed $B$ decider on its actual $\mathrm{\mid }q\mathrm{\mid }$-bit input using the constructible clock $T_q=\lceil K_2(\mathrm{\mid }q\mathrm{\mid }+2{)}^{e_j^{\mathrm{\prime }}}\rceil \ge \mathrm{\mid }q\mathrm{\mid }$. The normalized interpreter's index-only input reads are redirected to the encoded $q$ substring, returning the original blank or zero answer for addresses outside that substring; offsetting and saturating the emitted input indices is charged within the normalization bound. Its run takes $O(\mathrm{\mid }q{\mathrm{\mid }}^{e_j^{\mathrm{\prime }}}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{\mid }q\mathrm{\mid })=O(m)$ because $e_j^{\mathrm{\prime }}<e$. The sequential case reads the same encoded substring by local input moves within the same bound. Hence the padded language belongs to ${\mathrm{L}\mathrm{C}\mathrm{H}}_{P,1}$. The original linear-time oracle machine for ${\mathrm{L}\mathrm{C}\mathrm{H}}_{P,j+1}$ makes queries whose total lengths are $O(n)$. For $P=\mathrm{s}\mathrm{e}\mathrm{q}$, use that machine directly on the logical input $x$. For $P=\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}$, apply [F5] to its fixed code with a constructible clock $K_4(n+2)\ge n$; [F4] permits forwarding its exact completed oracle queries and answers. The resulting index-only simulation takes $O(n\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)$ time. Use a self-delimited padded input with the length and $x$ available in a designated prefix. The padded-language machine checks that encoding in $O(m)$ time; the index-only simulation redirects each logical input read to the encoded $x$ substring and returns the original blank/zero answer outside it. This offset handling is charged to the emitted input-index bits. Replace each query $q$ by its padded version of length $\mathrm{\Theta }((\mathrm{\mid }q\mathrm{\mid }+2{)}^e)$. The sum of these query lengths is $O({\sum }_q(\mathrm{\mid }q\mathrm{\mid }+2{)}^e)=O(n^e)$ because the original query lengths and query count sum to $O(n)$. Padding counters and query writes have the same total bound, so the padded outer language is decided in $O(m)$ time with oracle $B_e\in {\mathrm{L}\mathrm{C}\mathrm{H}}_{P,1}$ and hence lies in ${\mathrm{L}\mathrm{C}\mathrm{H}}_{P,2}$.

Apply the $m^{\rho }$ time decider from step 3.1 to that padded outer language, whose input is $y={\mathrm{pad}}_e(x)$ of length $m=\mathrm{\Theta }((n+2{)}^e)$. In the basis profile its block queries may again use long address blocks, so normalize this decider with [F5] at the constructible clock $T_m=\lceil K_3(m+2{)}^{\rho }\rceil \ge m$. Its exact index-only interpreter has time and physical work-access extent bounded by a constructible $T_m^{\mathrm{\prime }}=O(m^{\rho }\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}m)$. The bits of $y$ are generated from $x$ by the self-delimited prefix and zero-padding map in polylogarithmic time and logarithmic space; its padding length, the clocks, and the address majorants have polylog-time/logspace binary generators. Since $T_m^{\mathrm{\prime }}$ is polynomial in $n$, choose a constructible power-of-two address majorant $M_n=2^{\lceil K{\log }_2(n+2)\rceil }\le (n+2{)}^{K+1}$ and apply [F6] to simulate the normalized run on this generated input. The resulting time is $O((n+T_m^{\mathrm{\prime }}+1){\log }^{O(1)}(n+2))=O(n^{e\rho }\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)$. In the sequential profile, supply the same padded bits on demand to the sequential decider with at most polylogarithmic overhead per input transition. Choose rational $e_{j+1}^{\mathrm{\prime }}$ strictly between $e\rho$ and $e\delta ={\delta }^j$; the strict margin absorbs all polylogarithmic factors. This proves the induction assertion with its needed margin for the next padding step.

Steps 2.1 and 4.1–5.1 give ${\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n^b)\subseteq {\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}}_P(n^{{\delta }^{\tau -1}})$ although ${\delta }^{\tau -1}<b$. Both exponents are rational and strictly greater than or equal to one, so [F1] contradicts this containment. The two assumed deciders therefore cannot both exist. This proves the stated alternative in either fixed profile without converting a VMW time/space computation to a sequential one.