9
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ "PSPACE-complete problems must also take exponential time on a DTM" Must? That's not known to be the case. $\endgroup$
    – David Richerby
    Jun 18, 2015 at 19:40
  • 3
    $\begingroup$ In short: PSPACE-complete problems are (probably) harder than NP-complete problems. $\endgroup$
    – Yuval Filmus
    Jun 18, 2015 at 19:49
  • $\begingroup$ @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 $\endgroup$
    – Motorhead
    Jun 19, 2015 at 19:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – David Richerby
    Jun 19, 2015 at 19:10
  • 2
    $\begingroup$ @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$. $\endgroup$
    – David Richerby
    Jun 19, 2015 at 19:46

2 Answers 2

Reset to default
13
$\begingroup$

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!

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Motorhead
    Jun 19, 2015 at 19:04
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If you're interested in "practical" approaches to PSPACE-complete problems, this website has some good resources and libraries: languageinclusion.org/doku.php $\endgroup$
    – jmite
    Jun 18, 2015 at 20:20
  • $\begingroup$ 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. $\endgroup$
    – Raphael ♦
    Jun 19, 2015 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.