Show that $TIME(\sqrt{n})$ = $TIME(1)$

Question

Also known as CMU 15-455, Spring 2017, Homework 2.4.

Before I ask the main questions, let me first give a sketch of my idea. First, recall the definition of big-$O$ and time complexity class $TIME(t(n))$.

• Definition: Let $f$ and $g$ be functions $f$, $g$: $\mathbb{N}$ $\rightarrow$ $\mathbb{R}^+$. Say that $f(n)$ = $O(g(n))$ if $\lim_{n \to \infty}\dfrac{f(n)}{g(n)}$ = 0. In other words, $f(n) = O(g(n))$ means that for any real number $c$ > 0, a number $n_0$ exists, where $f(n)$ $\leq$ $cg(n)$ for all $n \geq n_0$.

• Definition: Let $t: \mathbb{N} \rightarrow \mathbb{R}^+$ be a function. Define the time complexity class, $TIME(t(n))$, to be the collection of all languages that are decidable by an $O(t(n))$ time Turing machine.

By definition, $TIME(\sqrt{n})$ and $TIME(1)$ are the collection of all languages that are decidable by a $O(\sqrt{n})$ and a $O(1)$ time TM respectively. My approach is the following:

Proposition: $TIME(1)$ is the collection of all languages that are decidable by an $O(\sqrt{n})$ time Turing machine.

If the above proposition is true, it should be sufficient to prove that $TIME(\sqrt{n})$ = $TIME(1)$. If the runtime is a constant $c$, then we can use the runtime $O(1)$ to represent $c$. Let $c = 1$ as an example. Obviously, $1$ = $O(1)$. We wish to show that $1$ = $O(\sqrt{n})$ as well.

By the definition of big-$O$, we have to prove that $\lim_{n\to\infty} \dfrac{1}{\sqrt{n}} = 0$, which is true. As such, $1$ = $O(1)$ = $O(\sqrt{n})$. As $TIME(1)$ is the collection of all languages that are decidable by an $O(1)$ time TM, and $O(1)$ = $O(\sqrt{n})$, the above proposition is proved. Hence $TIME(\sqrt{n})$ = $TIME(1)$.

The proof looks sound to me. However, upon further inspection, I have some problems with it:

1. The reverse approach, $TIME(\sqrt{n})$ is the collection of all languages decidable by an $O(1)$ time TM does not seem to work. Because if I understand the definition of big-$O$ correctly, are we trying to assert that $\sqrt{n}$ = $O(\sqrt{n})$ = $O(1)$? Then $\sqrt{n}$ = $1$, which is not true? What did I get wrong?

2. How can we show that $1 = O(1)$ with the definition of big-$O$ above? $\lim_{n\to\infty} \dfrac{1}{1} = 1 \neq 0$. And if we use the second version of the definition, what if $0 \leq c \leq 1$?

Those are my main question. In the case my approach is wrong, how will you approach it?

Answer 1

Suppose that a Turing machine runs in time at most $T(n)$ on inputs of length $n$, where $T(n) = o(n)$. Therefore $\lim_{n\to\infty} T(n)/n = 0$, and so we can find $N$ such that $T(n) < n$ for $n \geq N$.

Let $x$ be an input of size at least $N$, and let $y$ be the first $N$ symbols of $x$. If we run the Turing machine on $y$ then it halts in fewer than $N$ steps, and in particular, it doesn't reach end of the input. Therefore the Turing machine behaves exactly the same on $x$ and on $y$, and consequently, the running time on $x$ is also at most $T(N)$. Therefore the Turing machine halts on all inputs in time at most $\max(T(1),\ldots,T(N))$.

If instead of a Turing machine we had a random-access machine, then running times smaller than the input length do make sense. In such a setting, machines running in time $O(\sqrt{n})$ are indeed more powerful than those running in constant time.