This is a HW question that I'm stuck on and was hoping for some help. we're supposed to prove that:

PSPACE not equals DTIME($2^{cn}$) for every $c>0$ (or actually for the union of all $c>0$)

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you with the concepts but, with the question posed the way it is, the only way to answer it is to do your homework for you. $\endgroup$ – David Richerby Apr 13 '16 at 14:48
  • $\begingroup$ I honestly don't even know where to start. I thought of using TQBF and it's PSPACE completeness somehow but have no idea how to do that. $\endgroup$ – Olga Apr 13 '16 at 14:51

This can be proved by contradiction. You can use the fact that $PSPACE$ language remains $PSPACE$ if we remove polynomial length padding, where as $DTIME$ does not.

| cite | improve this answer | |
  • $\begingroup$ I will try to figure this out a bit later, just small question. how can you assume equality (line 3) for some c? I mean, different languages in PSPACE can require different c in the DTIME version. so just because I proved that this equality is wrong for a specific c, doesn't mean it's wrong for union of all c $\endgroup$ – Olga Apr 13 '16 at 14:49

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.