What are the known pseudo-polynomial PSPACE-complete problems?

Question

please can you provide either a reference, or give particular examples of PSPACE-complete problems which are solvable in pseudo-polynomial time?

Additonal Notes:

Definition of pseudo-polynomial time: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

In reply to some comments mentioned earlier. I have asked earlier if there were any problems which were PSPACE-complete which had an FPTAS. The surprizing answer was YES!

Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

This is therefore a follow-up question.

(Note that the EXP conjecture apply to the complexity class NP, yet there exists NP-complete problems which are solvable in psuedo-polynomial time!)

Addendum... Sasho Nikolov asked about FPT and Pspace. I know that there are FPT problems which are Pspace , Exp, Exp Space complete etc... Unfortunately I do not have references... Will correct when I remember

Thanks!!!

Zelah

Answer 1

Consider Subset Sum. A standard reduction from 3-SAT produces an instance with values $x_0,\ldots,x_{2n+1}$, where if there is a subset with the target sum, that set contains exactly one of $x_{2i},x_{2i+1}$ for each $i$. Furthermore, choosing $x_{2i}$ corresponds to setting the $i$th variable in the 3-SAT instance to true, and choosing $x_{2i+1}$ corresponds to setting it false. You can use this same reduction to reduce from quantified 3-SAT to result in a PSPACE-complete quantified version of subset sum, $\exists y_0 \forall y_1 \cdots \sum_{i}y_i = k$, where $y_i$ is equal to either $x_{2i}$ or $x_{2i+1}$.

You can use the same pseudo-polynomial time algorithm for subset sum on this quantified version with some minor modifications. We simply fill in a table of all sums $k$ such that $Q_iy_iQ_{i+1}y_{i+1}\cdots Q_ny_n\sum_{j=i}^{n}y_j = k$ (where each $Q_j$ is either $\exists$ or $\forall$). This table has only polynomial size if all the values are polynomially bounded, and it's not hard to see how to fill it in for $i-1$ given the values for $i$ - simply add $x_{2(i-1)}$ and $x_{2i-1}$ to all the values for $i$, and take either the union or intersection of these sets (for $\exists$ and $\forall$ quantifiers, respectively).

Answer 2

Isn't this just a matter of interpretation? Let $x \in \{0,1\}^*$ be an encoding of an instance of QBF. We can interpret $w = 1x$ as a number. If $w$ is given in binary, then this problem is essentially QBF. If we get $w$ in unary, then we have enough time to simulate the PSPACE machine for QBF. (We might need to pad with a polynomial number of bits, e.g. $w = 10...01x$.)

Even works for EXP.

Answer 3

My favorite example (due to Grzegorczyk):

Define $\mathcal G_2$ to be the closure of the following natural-number functions under composition and polynomial-bounded primitive recursion: $x + y, x y,$ projection (sending $(x, y)$ to $x$ or $y$), "cutoff-subtraction" $x \dot- y$ (it will return 0 if $y > x$), and the constant functions.

It is clear that any function in $\mathcal G_2$ is computable in pseudo-polynomial time; but it can be shown that a natural-number function is in $\mathcal G_2$ precisely if it is computable in deterministic linear space, viewing the inputs as binary strings. So evaluating an arbitrary expression of this form will be PSPACE-complete, but still pseudo-polynomial.