Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space.

Since we are unable to build nondeterministic or 'lucky' computers, does it make any difference to us if a problem is $NP$-complete or $PSPACE$-complete?

up vote 80 down vote accepted

This is a very nice question that I have thought about a lot: Does the fact that a problem is $NP$-complete or $PSPACE$-complete actually affect the worst-case time complexity of the problem? More fuzzily, does such a distinction really affect the "typical case" complexity of the problem in practice?

Intuition says that the $PSPACE$-complete problem is harder than the $NP$-complete one, regardless of what complexity measure you use. But the situation is subtle. It could be, for example, that $QBF$ (Quantified Boolean Formulas, the canonical $PSPACE$-complete problem) is in subexponential time if and only if $SAT$ (Satisfiability, the canonical $NP$-complete problem) is in subexponential time. (One direction is obvious; the other direction would be a major result!) If this is true, then maybe from the "I just want to solve this problem" point of view, it's not a big deal whether the problem is $PSPACE$-complete or $NP$-complete: either way, a subexponential algorithm for one implies a subexponential algorithm for the other.

Let me be a devil's advocate, and give you an example where one problem happens to be "harder" than the other, but yet turns out to be "more tractable" than the other as well.

Let $F(x_1,\ldots,x_{n})$ be a Boolean formula on $n$ variables, where $n$ is even. Suppose you have a choice between two formulas you want to decide:

$\Phi_1 = (\exists x_1)(\exists x_2)\cdots (\exists x_{n-1})(\exists x_{n})F(x_1,\ldots,x_{n})$.

$\Phi_2 = (\exists x_1)(\forall x_2)\cdots (\exists x_{n-1}(\forall x_{n})F(x_1,\ldots,x_{n})$

(That is, in $\Phi_2$, the quantifiers alternate.)

Which one do you think is easier to solve? Formulas of type $\Phi_1$, or formulas of type $\Phi_2$?

One would think that the obvious choice is $\Phi_1$, as it is only $NP$-complete to decide it, whereas $\Phi_2$ is a $PSPACE$-complete problem. But in fact, according to our best known algorithms, $\Phi_2$ is an easier problem. We have no idea how to solve $\Phi_1$ for general $F$ in less than $2^n$ steps. (If we could do this, we'd have new formula size lower bounds!) But $\Phi_2$ can be easily solved for any $F$ in randomized $O(2^{.793 n})$ time, using randomized game tree search! For a reference, see Chapter 2, Section 2.1, in Motwani and Raghavan.

The intuition is that adding universal quantifiers actually constrains the problem, making it easier to solve, rather than harder. The game tree search algorithm relies heavily on having alternating quantifiers, and cannot handle arbitrary quantifications. Still, the point remains that problems can sometimes get "simpler" under one complexity measure, even though they may look "harder" under another measure.

  • 16
    Nice answer, and an interesting take. – Suresh Venkat Mar 7 '11 at 23:49
  • It occurs to me that the above is a pretty good example of what we mean by "Fine-grained complexity" (a Fall 2015 program at the Simons Institute). One of the key ideas is that complexity theory can look quite different when, instead of trying to find for each problem a (potentially bizarre) computational model for which that problem is "complete", one simply focuses on understanding what is the best possible runtime exponent for the problem. – Ryan Williams Feb 28 '15 at 18:26

It does matter, because there is more at stake than whether or not we can find solutions. Also of interest is whether we can verify solutions. Other qualitiative distinctions can be made between the difficulty of problems, but for NP versus larger complexity classes, this would be the one I would identify as most important.

For decision problems — problems for which every instance has a 'YES' or 'NO' answer — NP is precisely the class of problems for which we can efficiently verify a purported proof that a given instance is a 'YES' instance, deterministically, if we are presented with one. For example, if you have a satisfying assignment of variables for an instance of 3-SAT, that assignment allows you to efficiently prove that the instance is satisfiable. Such a satisfying assignment may be hard to find, but once you have one, you can easily prove to others that the instance is satisfiable just by having them verify the solution you have found.

Similarly, for coNP, there exist efficiently checkable proofs for 'NO' instances; and for problems in NP ∩ coNP, you can do both. But for PSPACE-complete problems, no such procedures exist — unless you can prove some quite spectacular equalities of complexity classes.

  • I think that the question is about "optimization" version of NP-complete and PSPACE-complete problems. For instance, is there any difference (in terms of complexity) between finding a solution for SAT and for QBF? And more generally, is there a characterization of optimization problems of which decision version is NP-complete or PSPACE-complete? – Lamine Mar 7 '11 at 15:27
  • @Lamine: I don't I detect the distinction which you are making in the question (at least, between mere decision and full optimization). Perhaps you mean that the asker is only interested in the question of the resources required to find that the answer, and is untinterested in other measures of difficulty of the problem, in which case I agree that my response does not answer this. In any case, above is my answer for the question as it stands. – Niel de Beaudrap Mar 7 '11 at 15:33
  • 5
    Very nice answer. – Dave Clarke Mar 7 '11 at 15:44
  • The ability to verify efficiently does not help in computing a solution (unless P = NP). NP and co-NP allow attacking the problem via guess-and-verify. This approach is easy to implement, and may even be more efficient, but it doesn't help in the worst case. – András Salamon Mar 8 '11 at 14:11
  • @András: true — thus my emphasis that finding solutions is not the only important thing in the preface to my answer. – Niel de Beaudrap Mar 15 '11 at 9:34

We don't know how to build average-case hard problems from (worst-case) NP-complete problems but we can do this for PSPACE (see Köbler & Schuler (1998)) to create problems even over the uniform distribution that cannot be solved on most inputs unless all of PSPACE is easy to compute.

From a practical side, it's important to remember that NP-Completeness is not a barrier for many problems in practice. The twin tools of SAT solvers and CPLEX (for integer linear programming) are powerful enough and well-engineered enough that it's often possible to solve large instances of NP-complete problems by either framing the problem as a suitable ILP or by reduction to SAT.

I'm not aware of similarly well-engineered solvers for problems in PSPACE.

You might think of it this way: does a math problem have a proof that is human-readable, or does it inherently require a "computer proof." Examples: is the starting position of checkers a draw? (Answer: yes.) Is the starting position of chess a win for white? (Answer: unknown, but most gradmasters think it is a draw.)

The proof that the starting position of checkers is a draw ultimately requires one to accept that the computer really did accurately verify a lot of special cases. If a proof about chess ever exists, it will probably require human readers to accept that a computer correctly verified even more special cases. And it may well be that there is no shorter method to proof those statements. Those are problems in PSPACE. If a problem is "just" in NP, then (intuitively) a human being could hold the entire proof in his/her head. That human might need to be a very specialized mathematician, of course.

This metaphor will break down if pushed too hard -- an NP-proof of size $n^{1000000}$ probably won't ever fit into anyone's head. But the basic idea that "witnesses are small" is part of the reason NP-complete problems have so much industrial significance.

  • Could one also argue that coNP-complete problems have this problem of (sometimes) requiring a "computer proof?" – Philip White Mar 7 '11 at 19:32
  • @Philip White: I don't think it's the same. Say "chess a draw" is in coNP. To say no, all I have to do is to demonstrate a single forcing line that is easily verifiable. However, we expect that, even if such a line exists, it will probably be very hard to prove that it is indeed "forcing." So the problem gives no guarantee of simplicity if it is solvable in a particular direction. "Chess is a draw" probably inherently requires a computer to prove, whether it is true or false. – Aaron Sterling Mar 7 '11 at 22:03

Further to Suresh's comment, there appears to be a big difference in practice. There are heuristics that manage to exploit the structure of practical SAT instances and obtain excellent performance (I refer to conflict-driven clause learning solvers here). The same heuristics do not produce similar performance improvements in QBF solvers.

The difference between proof and verification also shows up. Some SAT solvers (such as MiniSAT 1.14 and a host of others) produce proofs. Producing proofs in current QBF solvers is non-trivial. (The next statement is from hearsay) There are large instances in the QBF competition on which solvers apparently produce different results. In the absence of proof-generating solvers, we do not know which result is correct.

If you look at practical performance on SAT and chess, then there is a difference -- NP-complete problems are more tractable than PSPACE-complete problems. SAT solvers today can handle over thousand variables, but the best chess engine, in the same amount of time, can only calculate under 20 moves.

I guess this is because of the structure of problems. Yes, if you just enumerate solutions, SAT solving is super slow. But because it does not have the quantifier alternation, people discover structures in the formula and hence avoid much of enumeration. I think Ryan Williams overlooked this point.

With quantifier alternation, yes there are smart methods of pruning, but still the structure is not as rich as that of a CNF formula.

Let me predict the future. SAT solving will make it to P by examining the formula and essentially avoiding search, while chess will make it to P by capitalizing on search in the game tree.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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