2
$\begingroup$

I have been reading Michael Sipser's Introduction to the Theory of Computation, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I simply do not understand.

For context, TQBF is the language of all first-order logical formulas in prenex normal form that are true given a universe/domain.

A language $B$ is PSPACE-complete if

  1. $B$ is in PSPACE, and
  2. every $A$ in PSPACE is polynomial time reducible to $B$.

The following paragraph from the book tells us that it is a bad idea to use Cook-Levin theorem for the purpose of showing that a language $A$ in PSPACE is polynomial time reducible to TQBF. The paragraph reads:

As a first attempt at this construction, let's try to imitate the proof of the Cook-Levin theorem, Theorem 7.37. We can construct a formula $\phi$ that simulates $M$ on input $w$ by expressing the requirements for the accepting tableau. A tableau for $M$ on input $w$ has width $O(n^k)$, the space used by $M$, but its height is exponential in $n^k$ because $M$ can run for exponential time. Thus, if we were to represent the tableau with a formula directly, we would end up with a formula of exponential size. However, a polynomial time reduction cannot produce an exponential-size result, so this attempt fails to show that $A$ is polynomial time reducible to TQBF.

This last sentence I don't get. Why cannot a polynomial time reduction produce an exponential size result? Doesn't any reductions using Cook-Levin from an NP language result in an exponential-size result? Is it that it doesn't work in this particular situation, or is this a general thing?

My guess is that it has to do with the assumed space complexities of $A$ or TQBF, however I still don't see it. One of the conditions for TQBF's PSPACE-completeness is to show that any PSPACE language is polynomial time reducible to TQBF. Any talk about space shouldn't really belong.

Maybe it's my sheer interpretation of the sentence?

$\endgroup$
3
$\begingroup$

If you want to write $N$ words of output, it takes at least $N$ steps of computation to do that. So, if you need to produce an exponential-sized output, you'll need to spend exponential time to do it. For that reason, a polynomial-time reduction cannot produce an exponential-sized output when run on a polynomial-sized input.

$\endgroup$
2
$\begingroup$

The fact that the given reduction takes exponential space implies it must take exponential time and therefore is not polynomial.

Using Cook-Levin on a NP-complete problem does not produce an exponential-sized output; it produces a polynomial-time circuit. It constructs a circuit whose size is polynomial in the number of steps taken by the NP-verifier; since the verifier runs in polynomial time, this circuit is polynomial in size.

$\endgroup$
1
  • $\begingroup$ But wouldn't this be true when we reduce an NP language B to SAT with Cook-Levin theorem? If B uses polynomial space, then simulating B on a Turing-machine that decides SAT will use exponential space. How come this is any more valid? $\endgroup$ – Snusifer May 11 at 18:35

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.