The complexity of matrix transposition on one-tape off-line Turing machines

AbstractThis paper contains the first concrete lower bound argument for Turing machines with one worktape and a two-way input tape (“one-tape off-line Turing machines”): an optimal lower bound of Ω(n·l/⌈(log(l)p)12⌉) for transposing an I × l-matrix with elements of bit length p on such machines is proved. (The length of the input is denoted by n.) A special case is a lower bound of Ω(n32(log n)12) for transposing Boolean l × l-matrices (n = l2) on such Turing machines. The proof of the matching upper bound (which is nontrivial for p