[Solved]: What is practical difference between NP and PSPACE-complete?

Problem Detail: 

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$\,\neq\,$NP, PSPACE$\,\neq\,$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?

Asked By : S.N.

Answered By : templatetypedef

I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to find an algorithm for that problem that is simultaneously worst-case efficient, deterministic, and always correct unless P = NP or P = PSPACE. Therefore, if you're just looking for whether the problem is efficiently solvable in all cases, both NP-hardness and PSPACE-hardness probably means that you're out of luck.

However, if that's not the lens you're looking through, then (based on the suspicion that NP ≠ PSPACE) there's a difference between NP-completeness and PSPACE-completeness. If a problem is NP-complete, then even if you can't solve the problem efficiently, you can still check "yes" answers efficiently. On the other hand, if NP ≠ PSPACE and you have an instance of a PSPACE-complete problem you're convinced has a "yes" answer, there might not be any efficient way to convince someone else of this.

Hope this helps!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43723