Lower Bounds by Kolmogorov-Complexity

Using Kolmogorov-complexity, we obtain the following new lower bounds. For on-line nondeterministic Turing machines, (1) simulating 2 pushdown stores by 1 tape requires $\Omega(n^{1.5} / logn)$ time; together with a newly proved $O( n^{1.5}\sqrt{logn})$ upper bound [L3], this basically settled the open problem 1 in [DGPR] for 1 tape vs. 2 pushdown case (the case of 1 tape vs. 2 tapes was basically settled by [M]); (2) simulating 1 queue by 1 tape requires $\Omega(n^{4/3} / logn)$ time; this brings us closer to a newly proved $O( n^{1.5}\sqrt{logn})$ upper bound [L3]; (3) simulating 2 tapes by 1 tape requires $\Omega(n^{2} / lognloglogn)$ time; this is a minor improvement of [M]'s $\Omega(n^{2} / log^{2}nloglogn)$ lower bound; it is also claimed (full proof contained in [L3]) that the actual languages used in [M] (also here) and [F] do not yield $\Omega(n^{2})$ lower bound. To cope with an open question of [GS] of whether a $k$-head 1-way DFA ($k$-DFA) can do string matching, we develop a set of techniques and show that 3-DFA cannot do string matching, settling the case $k = 3$. Some other related lower bounds are also presented