# Problem in computational complexity (superior class)

Say that a class $$C_1$$ is superior to a class $$C_2$$ if there is a machine $$M_1$$ in class $$C_1$$ such that for every machine $$M_2$$ in class $$C_2$$ and every large enough $$n$$, there is an input of size between $$n$$ and $$n^2$$ on which $$M_1$$ and $$M_2$$ answer differently.

1. Is DTIME($$n^{1.1}$$) superior to DTIME($$n$$)?

2. Is NTIME($$n^{1.1}$$) superior to NTIME($$n$$)?

This is an exercise from book Computational Complexity: A Modern Approach. But I have no idea to handle it. Does it have relationship with theorem that DTIME$$(n)$$ $$\subsetneqq$$ DTIME($$n^{1.5}$$)?

• Is the large enough $n$ independent of $M_2$? Or can it be different for every $M_2$? Mar 23, 2016 at 4:59
• I think they are independent. So the negation is $\exists M_2$ and $n$, s.t. $M_1(x)=M_2(x), \forall x \in \{x: n<|x|<n^2\}$ Mar 23, 2016 at 5:46
• Take a closer look at the proof of the time hierarchy theorem. Mar 23, 2016 at 6:44
• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. Mar 23, 2016 at 9:08

The proof of the time hierarchy theorems can be paraphrased like this. We want to show that $\mathsf{X} \subsetneq \mathsf{Y}$ for appropriate $\mathsf{X},\mathsf{Y}$. The idea is to construct a diagonalizing machine $M \in \mathsf{Y}$ (slight abuse of notation here) whose language is different from all languages in $\mathsf{X}$. On input $x$, the machine $M$ runs $x$ on $x$ up to some specified time bound, and then answers the opposite. If the simulation is efficient enough, $M \in \mathsf{Y}$.
• If $n$ is indeed independent of $M_2$ then I think it is tough to prove the propositions. At least $DTIME(n^{1.1})$ won't be superior to $DTIME( (1+\epsilon)n+2)$ by linear speedup theorem. Mar 23, 2016 at 11:41
• Say $n=N$ is the large enough $n$ in question. Then we can construct a machine that runs $M_1$ for strings of length between $N$ and $N^2$ and any other $DTIME((1+\epsilon)n+2)$ machine for other lengths. The resulting machine is $DTIME( \max\{(1+\epsilon)n+2, N^{2.2}\})$ which is a $DTIME((1+\epsilon)n+2)$ by linear speedup theorem. Mar 23, 2016 at 11:47
• The value of $n$ is allowed to depend on $M_2$. That's the order of quantifiers in the question: for every $M_2$ there is a large enough $n$. If they wanted "large enough" to be uniform, they would have switched these quantifiers. Mar 23, 2016 at 13:39