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

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

CC BY-SA 3.0
2011-05-06T18:49:11.243Z
2011-05-06T18:49:11.243Z
Dave
<p>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$.)</p>

<p>Even works for EXP.</p>

CC BY-SA 3.0
2011-05-06T09:51:15.993Z
If $w$ is unary, then the problem isn't PSPACE complete anymore, because you can't construct the unary input for QBF in polynomial time.
Marc Bury
CC BY-SA 3.0
2011-05-06T10:09:58.013Z
But doesn't pseudopolynomial mean that the running time is polynomial in the size of the weights (rather than the size of the description of the weights) which is the same as the description size if the weights are given in unary?
5501
CC BY-SA 3.0
2011-05-06T14:16:03.020Z
@5501 What I mean is that the proof that QBF is PSPACE-complete doesn't work anymore if the input for QBF is given in unary.
Marc Bury
CC BY-SA 3.0
2011-05-06T14:42:36.370Z
@Marc Gille Of course, the problem is the one with the inputs given in binary. This is PSPACE-complete. And a pseudopolynomial time algorithm is an algorithm that runs in polynomial time if the weights are given in unary. If you have a Knapsack instance with weights in unary, then the NP-completeness proof does not work either. In short: completeness = weights given in binary, pseudopolynomial algorithm = weights in unary.
5501
CC BY-SA 3.0
2011-05-06T14:53:31.187Z
@5501 what you describe can put virtually any language in $P$: make anything unary, if you need more time, enough just pad. 

i believe it makes sense to say a problem has a pseudopolynomial time algorithm if there is a natural numerical parameter and the algorithm is polynomial in that parameter (rather than in its bit representation). Like the knapsack problem with bounded integer weights. or a brute force factoring algorithm. i suppose that's an FPT related question. anyone with FPT expertise?
Sasho Nikolov
CC BY-SA 3.0
2011-05-06T16:24:24.877Z
Of course, the problem is artifical. But the answer to the previous question was artifical, too. On the other hand: "What is a good definition of natural?". Papadimitriou's book Computational Complexity, apge 216 is quite interesting.
5501
CC BY-SA 3.0
2011-05-06T08:24:28.190Z
2011-05-06T08:24:28.190Z
5501
<p>My favorite example (due to Grzegorczyk):</p>

<p>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 &gt; x$), and the constant functions.</p>

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

CC BY-SA 3.0
2012-09-03T05:07:02.397Z
2012-09-03T05:07:02.397Z
Ben Standeven
<p>please can you provide either a reference, or give particular examples of PSPACE-complete problems which are solvable in pseudo-polynomial time?</p>

<p>Additonal Notes:</p>

<p>Definition of pseudo-polynomial time: <a href="http://en.wikipedia.org/wiki/Pseudo-polynomial_time" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Pseudo-polynomial_time</a></p>

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

<p><a href="https://cstheory.stackexchange.com/questions/2647/does-there-exist-a-particular-pspace-complete-problem-which-has-a-fptas-algorithm">Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?</a></p>

<p>This is therefore a follow-up question.</p>

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

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

<p>Thanks!!!</p>

<p>Zelah </p>

CC BY-SA 3.0
2011-05-04T13:18:34.573Z
the [exponential time hypothesis](http://en.wikipedia.org/wiki/Exponential_time_hypothesis) suggests that such problems might be hard to come by, but I am not an expert.
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-04T15:24:49.883Z
What do you mean by a problem being pseudopolynomial?  I voted to close the question as off topic, assuming that you meant a PSPACE-complete problem which can be solved in pseudopolynomial time (such a problem obviously does not exist if PSPACE⊈DTIME[2^(polylog n)], which is a much weaker hypothesis than the exponential time hypothesis).  If my assumption is not correct, I may (virtually) take back my close vote.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-04T20:16:32.207Z
Zelah, it might help if you explain why you are interested in the question, otherwise I agree with Tsuyoshi's comment (and IMO the question should be closed as not a real question).
Kaveh
CC BY-SA 3.0
2011-05-05T12:50:04.310Z
@Tsuyoshi, @Artem: Are you guys confusing pseudo-polynomial with quasi-polynomial?
Robin Kothari
CC BY-SA 3.0
2011-05-05T16:42:46.480Z
@Robin: Yes, I was confusing pseudo-polynomial with quasi-polynomial.  Thanks for pointing it out.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-06T00:26:45.980Z
@Robin: So was I, my bad!
Artem Kaznatcheev
<cc.complexity-theory><complexity-classes>
What are the known pseudo-polynomial PSPACE-complete problems?
Zelah 02
# What are the known pseudo-polynomial PSPACE-complete problems?

(Asked by: username_0 on 2011-05-04)

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?](https://cstheory.stackexchange.com/questions/2647/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...
username_8 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

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: the [exponential time hypothesis](http://en.wikipedia.org/wiki/Exponential_time_hypothesis) suggests that such problems might be hard to come by, but I am not an expert.  
> **username_2**: What do you mean by a problem being pseudopolynomial?  I voted to close the question as off topic, assuming that you meant a PSPACE-complete problem which can be solved in pseudopolynomial time (such a problem obviously does not exist if PSPACE⊈DTIME[2^(polylog n)], which is a much weaker hypothesis than the exponential time hypothesis).  If my assumption is not correct, I may (virtually) take back my close vote.  
> **username_3**: Zelah, it might help if you explain why you are interested in the question, otherwise I agree with Tsuyoshi's comment (and IMO the question should be closed as not a real question).  
> **username_4**: @Tsuyoshi, @Artem: Are you guys confusing pseudo-polynomial with quasi-polynomial?  
> **username_2**: @Robin: Yes, I was confusing pseudo-polynomial with quasi-polynomial.  Thanks for pointing it out.  
> **username_1**: @Robin: So was I, my bad!  

---

## 3 answers

### Answer by username_5 on 2011-05-06. Score: 5 | Accepted answer

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 by username_6 on 2011-05-06. Score: 1

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.

> **Comments:**
> **username_7**: If $w$ is unary, then the problem isn't PSPACE complete anymore, because you can't construct the unary input for QBF in polynomial time.  
> **username_6**: But doesn't pseudopolynomial mean that the running time is polynomial in the size of the weights (rather than the size of the description of the weights) which is the same as the description size if the weights are given in unary?  
> **username_7**: @username_6 What I mean is that the proof that QBF is PSPACE-complete doesn't work anymore if the input for QBF is given in unary.  
> **username_6**: @Marc Gille Of course, the problem is the one with the inputs given in binary. This is PSPACE-complete. And a pseudopolynomial time algorithm is an algorithm that runs in polynomial time if the weights are given in unary. If you have a Knapsack instance with weights in unary, then the NP-completeness proof does not work either. In short: completeness = weights given in binary, pseudopolynomial algorithm = weights in unary.  
> **username_8**: @username_6 what you describe can put virtually any language in $P$: make anything unary, if you need more time, enough just pad.   i believe it makes sense to say a problem has a pseudopolynomial time algorithm if there is a natural numerical parameter and the algorithm is polynomial in that parameter (rather than in its bit representation). Like the knapsack problem with bounded integer weights. or a brute force factoring algorithm. i suppose that's an FPT related question. anyone with FPT expertise?  
> **username_6**: Of course, the problem is artifical. But the answer to the previous question was artifical, too. On the other hand: "What is a good definition of natural?". Papadimitriou's book Computational Complexity, apge 216 is quite interesting.  

---

### Answer by username_9 on 2012-09-03. Score: 1

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.


---

