Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing.
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?
Well as far as I see it. The practical difference is the functionality of time. The closer to the halting problem the longer the run....even if they equate. Unless provided with infinite time and space which wouldn't even be feasible let alone practical.