# Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?

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?

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.