Computational Complexity HT25, Crossing sequences

The sequence of states the TM is in during visits to the tape cell.

Not so sure about this…

Consider any 1-tape TM $M$ deciding $\mathsf{PAL}$, and consider inputs of the form $f(x) = x 0^m x^R$, where $x$ is a string of length $m$.

Suppose there were distinct $x, y$ of length $m$ such that $f(x)$ and $f(y)$ have the same crossing sequence at some tape cell $i$ and cell $j$ in the middle block. Then $M$ would accept $x 0^m y^R = x’ y’$ where $x’$ is the first $i$ characters of $x$ and $y’$ is the last $ \vert y \vert - j$ characters of $y$ (this is intuitive but difficult to formalise). This string is not in $\mathsf{PAL}$, and hence each $x$ must distinct crossing sequences at all the cells in the middle block, so there must be $2^m$ distinct crossing sequences at cell $i$ in the middle block.

For each input $f(x)$ where $ \vert x \vert = m$, some cell in the middle block must have crossing sequence at most $T(3m) / m$, since otherwise the run time would be more than $T(3m) = T(n)$, a contradiction. Call this cell “the cell with the short crossing sequence on $f(x)$”.

The total number of crossing sequences of length $\ell = T(3n) / n$ is

\[\sum^\ell_{i = 0} |Q|^i \le |Q|^{\ell + 1}\]

For each of the $2^m$ possible $x$, there must be the cell with the short crossing sequence on $f(x)$. By the above, each of these cells with short crossing sequences must have distinct crossing sequences. Therefore

\[\begin{aligned} &|Q|^{\ell + 1} \ge 2^n &&(\text{otherwise they can't all be distinct}) \\\\ \implies&\ell + 1 \ge n \log_{|Q|}(2) \\\\ \implies&\frac{T(3n)}{n} \ge n \log_{|Q|} (2) - 1 \\\\ \implies&T(3n) \ge n^2\log_{|Q|}(2) - 1 \end{aligned}\]

and hence $T(n) = \Omega(n^2)$, a contradiction.

@sheets~ @example~