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?
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.
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.
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.
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.
