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?
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
cc.complexity theory;np hardness;big picture
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.