Is there an easy way (maybe by using hierarchy theorems) to disprove that $DTIME(f) = NSPACE(f)$ for any computable $f: \mathbb{N}\rightarrow\mathbb{N}$ with $f(n)\geq n$?

  • $\begingroup$ Try diagonalization. Follow the proofs of the time and space hierarchy theorems. $\endgroup$ – Yuval Filmus Sep 3 '18 at 23:10

Your Answer

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

Browse other questions tagged or ask your own question.