1
$\begingroup$

I am trying to understand the space and time Hierarchy theorems according to

Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach

but the more general case.

What I don't understand is why the language decided by our custom machine is in the larger complexity class. For example, with the case of time complexity, the cost of simulating the input machine is $t_1 \log t_1$, so why is the language decided by it in $DTIME(t_2)$ but not in $DTIME(t_1 \log t_1)$?

thanks

Improve this question
$\endgroup$
2
  • $\begingroup$ I am not sure whether you understood the time hierarchie theorem correctly. You want to distinguish $DTIME(t_1)$ (not $DTIME(t_1 \log t_1)$!) from $DTIME(t_2)$. The logarihmic overhead is just for the simulation of your Turing machine. $\endgroup$
    – ttnick
    Apr 25, 2018 at 13:32
  • $\begingroup$ Yes, I understand that but we make an assumption that $t_2$ is asymptotically larger than $t_1log_t1$, but in the proof it seems that the runtime of the machine is $t_1logt_1$. Actually the space version is simpler for me to explain: we assume $s_2$ is asymptotically larger, but the simulation costs $s_1$, so I don't understand why just from the description it doesn't run in $s_1$ space. $\endgroup$
    – Eloo
    Apr 25, 2018 at 13:52

2 Answers 2

Reset to default
1
$\begingroup$

A rich man walks into a bar and says, "I can buy this beer because I am a millionaire." Eloo says, "The beer costs \$5. I don't understand why this millionaire can buy it, but this guy with five dollars can't."

Remember that $\mathrm{DTIME}[f(n)]$ is the class of languages that can be decided by a deterministic Turing machine that uses at most $f(n)$ steps on any input of length $n$. So, since $t_1\log t_1\leq t_2$, anything in $\mathrm{DTIME}[t_1\log t_1]$ is in $\mathrm{DTIME}[t_2]$.

Improve this answer
$\endgroup$
0
$\begingroup$

So after looking into it again I realized that if we give the machine any amount of additional time asymptotically (any time asymptotically larger than $t_1\log t_1$), then we can construct a language for it because it will accept the machine of the language and we can also add all the machines that reject their own description to that language too.

Improve this answer
$\endgroup$

Your Answer

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

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