title: Confusion about why NP is contained in PSPACE, EXPTIME etc
body: <p>Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. </p>
  
  <p>Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P /= NP, PSPACE /= NP etc. this means that there are NP-complete problems that cannot be solved in polynomial time on a DTM. Which means that either they have some complexity that lies between polynomial and exponential (which I am not sure what that might be) or they must take exponential time on a DTM (and no more than polynomial space). If its the latter, then consider the PSPACE-complete problems. A problem is in PSPACE if it can be solved using a polynomial amount of space. Since NP \subseteq PSPACE \subseteq EXPTIME, PSPACE-complete problems must also take exponential time on a DTM. Then what is the practical difference between NP-complete and PSPACE-complete problems?</p>