2
$\begingroup$

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$).

Why do we have these conditions?

$\endgroup$
  • $\begingroup$ Presumably the proof doesn't work without these conditions, and perhaps the result itself isn't true. $\endgroup$ – Yuval Filmus May 26 '16 at 12:33
  • $\begingroup$ when we set the condition: being fully space( time) constructible, we dont need to the condition being greater than log(n), because i think all fully space constructible functions are greater than log(n). Am i right? $\endgroup$ – Yuval May 26 '16 at 12:43
  • $\begingroup$ Constant functions are also fully space constructible. There are other examples which are not constant. $\endgroup$ – Yuval Filmus May 26 '16 at 13:08
  • $\begingroup$ hmm, you're right, so why is there? exept these two hierarchy theorem in other theorems exist these condition! i'm interested in that. whenever we want to say a theorem about space (time) we set the condition being greater than log(n) (n)! $\endgroup$ – Yuval May 26 '16 at 13:14
2
$\begingroup$

A concise answer would be: To have enough time (resp. space) to do the diagonalization jobs.

Remember that both of these separation results are just using diagonalization techniques. In particular, to separate bigger time/space bound apart smaller time/space bound, one use the bigger bound (by just ONE machine) to diagonalize over all the possible smaller time/space-bounded machines.

And to do that, one needs to know when to finish (on each input) in case of time hierarchy, or where to prohibit the crossing (on each input) in case of space hirachy. This is possible only when the bigger bound is constructible. For time, constructibility at least requires $\geq n$. For space, constructibility at least requires $\geq log(n)$.


For full constructibility, it is not necessary to require any thing. But note that while constant functions are fully constructible (in time and space), functions in between like $log log(n)$, $log log log(n)$ (for space), $\sqrt{(n)}$, $n^{2/3}$ (for time) are not so. Informally, the spectrum of full constructibility is not continuous.

Lastly, one can even separate the notions of time constructibility by reasonable conjectures.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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