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

<p>For decision problems &mdash; problems for which every instance has a '<em>YES</em>' or '<em>NO</em>' answer &mdash; <strong>NP</strong> is precisely the class of problems for which we can efficiently verify a purported proof that a given instance is a '<em>YES</em>' 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.</p>

<p>Similarly, for <strong>coNP</strong>, there exist efficiently checkable proofs for '<em>NO</em>' instances; and for problems in <strong>NP</strong>&nbsp;&cap;&nbsp;<strong>coNP</strong>, you can do both. But for <strong>PSPACE</strong>-complete problems, no such procedures exist &mdash; unless you can prove some quite spectacular equalities of complexity classes. </p>

CC BY-SA 2.5
2011-03-07T15:27:55.697Z
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
CC BY-SA 2.5
2011-03-07T15:33:00.697Z
@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
CC BY-SA 2.5
2011-03-07T15:44:39.443Z
Very nice answer.
Dave Clarke
CC BY-SA 2.5
2011-03-08T14:11:44.617Z
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
CC BY-SA 2.5
2011-03-15T09:34:11.093Z
@András: true — thus my emphasis that finding solutions is not the only important thing in the preface to my answer.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-07T15:13:29.853Z
2011-03-07T15:19:48.787Z
2011-03-07T15:19:48.787Z
Niel de Beaudrap
<p>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 <a href="http://www.springerlink.com/content/h765k25486510253">Köbler &amp; Schuler (1998)</a>) to create problems even over the uniform distribution that cannot be solved on most inputs unless all of PSPACE is easy to compute.</p>

CC BY-SA 3.0
2011-03-08T12:58:07.327Z
2014-03-09T05:53:26.780Z
2014-03-09T05:53:26.780Z
Lance Fortnow
<p>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. </p>

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

CC BY-SA 2.5
2011-03-08T13:18:42.583Z
There is a [yearly competition designed to improve QBF solvers](http://www.qbflib.org/index_eval.php). I did not use them much.
Radu GRIGore
CC BY-SA 2.5
2011-03-07T17:15:59.067Z
2011-03-07T17:15:59.067Z
Suresh Venkat
<p>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.)</p>

<p>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 <em>no shorter method</em> 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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-07T22:03:43.913Z
@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
CC BY-SA 2.5
2011-03-07T17:12:41.793Z
2011-03-07T17:12:41.793Z
Aaron Sterling
<p>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. </p>

<p>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.</p>

CC BY-SA 2.5
2011-03-07T23:28:36.450Z
2011-03-07T23:28:36.450Z
Vijay D
<p>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.</p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2011-07-26T13:34:49.113Z
2011-07-26T13:34:49.113Z
Zirui Wang
<p>This is a very nice question that I have thought about a lot: <strong>Does the fact that a problem is $NP$-complete or $PSPACE$-complete actually affect the worst-case time complexity of the problem?</strong> More fuzzily, does such a distinction really affect the "typical case" complexity of the problem in practice?</p>

<p>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.</p>

<p>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. </p>

<p>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:</p>

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

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

<p>(That is, in $\Phi_2$, the quantifiers alternate.)</p>

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

<p>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. </p>

<p>The intuition is that <em>adding universal quantifiers actually constrains the problem</em>, making it <em>easier</em> 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.</p>

CC BY-SA 2.5
2011-03-07T23:49:24.213Z
Nice answer, and an interesting take.
Suresh Venkat
CC BY-SA 3.0
2015-02-28T18:26:02.270Z
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
CC BY-SA 3.0
2011-03-07T23:06:01.740Z
2014-03-09T21:27:51.927Z
2014-03-09T21:27:51.927Z
Ryan Williams
<p>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.</p>

<p>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?</p>

<cc.complexity-theory><np-hardness><big-picture>
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
Alex ten Brink
# Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

(Asked by: username_0 on 2011-03-07)

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?

**Tags:** cc.complexity-theory, np-hardness, big-picture

---

## 7 answers

### Answer by username_11 on 2011-03-07. Score: 88 | Accepted answer

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.

> **Comments:**
> **username_6**: Nice answer, and an interesting take.  
> **username_11**: 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.  

---

### Answer by username_1 on 2011-03-07. Score: 37

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.

> **Comments:**
> **username_2**: 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?  
> **username_1**: @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.  
> **username_3**: Very nice answer.  
> **username_4**: 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.  
> **username_1**: @András: true — thus my emphasis that finding solutions is not the only important thing in the preface to my answer.  

---

### Answer by username_5 on 2011-03-08. Score: 36

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)](http://www.springerlink.com/content/h765k25486510253)) to create problems even over the uniform distribution that cannot be solved on most inputs unless all of PSPACE is easy to compute.


---

### Answer by username_6 on 2011-03-07. Score: 20

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.

> **Comments:**
> **username_7**: There is a [yearly competition designed to improve QBF solvers](http://www.qbflib.org/index_eval.php). I did not use them much.  

---

### Answer by username_8 on 2011-03-07. Score: 6

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.

> **Comments:**
> **username_8**: @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.  

---

### Answer by username_9 on 2011-03-07. Score: 5

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.


---

### Answer by username_10 on 2011-07-26. Score: 0

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.


---

