I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$.

There isn't a solution provided in the textbook. I've been working with a solution involving padding but I haven't been able to come up with a solution.

Any tips would be appreciated! Thanks in advance.

  • $\begingroup$ Try mimicking the proof of your favorite hierarchy theorem. $\endgroup$ – Yuval Filmus Mar 31 '18 at 17:44

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.