1
$\begingroup$

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}$)?

$\endgroup$
4
  • $\begingroup$ Is the large enough $n$ independent of $M_2$? Or can it be different for every $M_2$? $\endgroup$ Mar 23, 2016 at 4:59
  • $\begingroup$ 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\}$ $\endgroup$
    – Atom Lee
    Mar 23, 2016 at 5:46
  • $\begingroup$ Take a closer look at the proof of the time hierarchy theorem. $\endgroup$ Mar 23, 2016 at 6:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Mar 23, 2016 at 9:08

1 Answer 1

2
$\begingroup$

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}$.

Your question is very similar. Go over the proof of the time hierarchy theorems, and check whether the diagonalizing machines there fit your bill.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Mar 23, 2016 at 11:41
  • $\begingroup$ 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. $\endgroup$ Mar 23, 2016 at 11:47
  • $\begingroup$ 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. $\endgroup$ Mar 23, 2016 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.