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
- $B$ is in PSPACE, and
- 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?