8
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ the exponential time hypothesis suggests that such problems might be hard to come by, but I am not an expert. $\endgroup$ – Artem Kaznatcheev May 4 '11 at 13:18
  • 5
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito May 4 '11 at 15:24
  • 5
    $\begingroup$ @Tsuyoshi, @Artem: Are you guys confusing pseudo-polynomial with quasi-polynomial? $\endgroup$ – Robin Kothari May 5 '11 at 12:50
  • 2
    $\begingroup$ @Robin: Yes, I was confusing pseudo-polynomial with quasi-polynomial. Thanks for pointing it out. $\endgroup$ – Tsuyoshi Ito May 5 '11 at 16:42
  • 2
    $\begingroup$ @Robin: So was I, my bad! $\endgroup$ – Artem Kaznatcheev May 6 '11 at 0:26
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – 5501 May 6 '11 at 10:09
  • 1
    $\begingroup$ @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. $\endgroup$ – Marc Bury May 6 '11 at 14:16
  • 1
    $\begingroup$ @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. $\endgroup$ – 5501 May 6 '11 at 14:42
  • 2
    $\begingroup$ @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? $\endgroup$ – Sasho Nikolov May 6 '11 at 14:53
  • 2
    $\begingroup$ 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. $\endgroup$ – 5501 May 6 '11 at 16:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.