Counting Hierarchy Time Space Lower Bound

Fix $d,\epsilon$ and choose rational $D>\max (d,1)$ and rational $0<{\epsilon }^{\mathrm{\prime }}<\min (\epsilon ,1)$. By [F2] there is a classical time exponent $C>1$ for the alternative with parameters $D,{\epsilon }^{\mathrm{\prime }}$. Choose rational $1<c<C$ and suppose, for contradiction, that both quantum algorithms in the statement exist. For the time-only $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ algorithm, choose rational ${\tau }_{\mathrm{m}\mathrm{m}}$ with $c<{\tau }_{\mathrm{m}\mathrm{m}}<C$ and use the constructible simulation clock $t_{\mathrm{m}\mathrm{m}}=\lceil K_{\mathrm{m}\mathrm{m}}(n+2{)}^{{\tau }_{\mathrm{m}\mathrm{m}}}\rceil$. The published VMW model permits maximum work addresses exponential in the running time: in $t_{\mathrm{m}\mathrm{m}}$ transitions only $O(t_{\mathrm{m}\mathrm{m}})$ address bits can be emitted, so a constructible space majorant $s_{\mathrm{m}\mathrm{m}}=2^{K{t}_{\mathrm{m}\mathrm{m}}}$, for a fixed sufficiently large $K$, bounds every work operand and query endpoint of this fixed machine. Its binary numeral is a $1$ followed by $K{t}_{\mathrm{m}\mathrm{m}}$ zeroes and is generated in $O(t_{\mathrm{m}\mathrm{m}})$ time, within the required constructibility bounds. Both $t_{\mathrm{m}\mathrm{m}},s_{\mathrm{m}\mathrm{m}}\ge \log n$, so [F1] gives a matching-profile classical time $O(n^{{\tau }_{\mathrm{m}\mathrm{m}}}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)\subseteq O(n^C)$ decider. For the $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ algorithm, choose rational ${\tau }_{\mathrm{s}\mathrm{a}\mathrm{t}}$ with $\max (d,1)<{\tau }_{\mathrm{s}\mathrm{a}\mathrm{t}}<D$ and use constructible majorants $t_{\mathrm{s}\mathrm{a}\mathrm{t}}=\lceil K_{\mathrm{s}\mathrm{a}\mathrm{t}}(n+2{)}^{{\tau }_{\mathrm{s}\mathrm{a}\mathrm{t}}}\rceil$ and $s_{\mathrm{s}\mathrm{a}\mathrm{t}}=\lceil K_{\mathrm{s}\mathrm{a}\mathrm{t}}^{\mathrm{\prime }}(n+2{)}^{1-{\epsilon }^{\mathrm{\prime }}}\rceil$. They are at least $\log n$ for large $n$ and dominate the assumed time $O(n^d)$ and space $O(n^{1-\epsilon })$. Theorem [F1] then gives classical time $O(n^{{\tau }_{\mathrm{s}\mathrm{a}\mathrm{t}}}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)\subseteq O(n^D)$ and space $O(n^{1-{\epsilon }^{\mathrm{\prime }}}+\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)\subseteq O(n^{1-{\epsilon }^{\mathrm{\prime }}})$. These two classical algorithms contradict both sides of [F2]'s alternative.

Suppose $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ has time $n^{1+o(1)}$ and space $O(n^{1-\epsilon })$. By [F3], a plain $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ encoding is already the identical bit string accepted as a $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ instance with an implicit fresh unused outer variable. Both of its outer assignments have the original inner majority value. First validate the plain encoding in $O(n\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)$ time and $O(\log n)$ workspace, rejecting malformed or partition-tagged inputs. On a valid plain input, reset that scratch and run the assumed quantum algorithm on the identical bit string, with exactly the same coherent input oracle and bounded error. Total time remains $n^{1+o(1)}$ and space is $O(n^{1-\epsilon }+\log n)$; no coherent virtual-input compilation is required. Choose $0<{\epsilon }^{\mathrm{\prime }\mathrm{\prime }}<\min (\epsilon ,1)$ and any fixed $d>1$. These resources meet $O(n^d)$ and $O(n^{1-{\epsilon }^{\mathrm{\prime }\mathrm{\prime }}})$. The original $\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{M}\mathrm{a}\mathrm{j}\mathrm{S}\mathrm{A}\mathrm{T}$ algorithm also meets $O(n^c)$ for every fixed $c>1$, contradicting the disjunction of step 1.1 with parameters $d,{\epsilon }^{\mathrm{\prime }\mathrm{\prime }}$. This proves the corollary.