# What is practical difference between NP and PSPACE-complete?

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?

• "PSPACE-complete problems must also take exponential time on a DTM" Must? That's not known to be the case. – David Richerby Jun 18 '15 at 19:40
• In short: PSPACE-complete problems are (probably) harder than NP-complete problems. – Yuval Filmus Jun 18 '15 at 19:49
• @DavidRicherby: If by my assumption NP /= P, then they must take at least exponential time and they must take no more than exponential time or PSPACE wouldn't be contained in EXPTIME – S.N. Jun 19 '15 at 19:07
• @user1721431 They can't take more than exponential time, agreed. But "must take exponential time" sounds like a lower bound, to me. It's perfectly possible that P, NP, PSPACE and EXPTIME are all distinct, in which case PSPACE woudln't seem to require exponential time. – David Richerby Jun 19 '15 at 19:10
• @S.N. Something like $2^{(\log n)^k}$ for some constant $k$ is intermediate between polynomial and exponential. Any exponential grows faster than any polynomial. You can write, e.g., $\mathrm{e}^x = \sum_{n=0}^\infty x^n/n!$, which holds for all $x$ but that's an infinite sum, not a polynomial. If you truncate the series at any point, it fails for large enough $x$. – David Richerby Jun 19 '15 at 19:46

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!

• Yes that is the answer I was looking for. Sorry I don't have enough reputation to upvote this answer or I would. perhaps someone else who agrees can do so – S.N. Jun 19 '15 at 19:04

The main practical implication is that PSPACE-complete problems are probably even harder than NP-complete problems.

With NP-complete problems, you at least have some small hope to solve them with a SAT solver, an ILP solver, or with other methods. With PSPACE-complete problems, a SAT solver or ILP solver probably won't work (at SAT can only express problems in NP; PSPACE-complete problems cannot be formulated as an instance of SAT), and many other methods for dealing with NP-completeness are less likely to work.

If you're interested in "practical" approaches to PSPACE-complete problems, this site has some resources for solving some PSPACE-complete problems... though you shouldn't necessarily expect it to be as effective as SAT solvers have been for NP-complete problems, given that PSPACE-complete problems are believed to be harder than NP-complete problems.

• If you're interested in "practical" approaches to PSPACE-complete problems, this website has some good resources and libraries: languageinclusion.org/doku.php – jmite Jun 18 '15 at 20:20
• This reference question lists some approaches to solving NP-complete problems in practice. If this answer is correct, none of them (?) should work for your PSPACE-complete problem of choice. – Raphael Jun 19 '15 at 11:23