# Why can't $QBF$ be reduced to $SAT$

Let $$QBF_k$$ be the problem of determining the satisfiability of a formula of the form $$Φ = Q_1x_1Q_2x_2 . . . Q_kx_k φ(x_1, . . . , x_n)$$. where each $$Q_i$$ is one of the quantifiers $$∀$$ or $$∃$$. So, $$Φ$$ contains $$k$$ quantified variables $$x_1, . . . , x_k$$ and free variables $$x_{k+1}, . . . , x_n$$. The problem $$QBF_k$$ is to determine where $$Φ$$ evaluates to true for some value of the free variables $$x_{k+1}, . . . , x_n$$. φ is any propositional formula built up from the usual connectives and, or, not.

I know that $$QBFk ≤_p QBF_{k−1}$$

(Every $$\exists$$ quantifier can be made into 2 formulas connected with an or, while every $$\forall$$ quantifier can be made into a formula connected by an and)

What is wrong with the following argument: “Since $$QBF_k ≤_p QBF_{k−1}$$ for any $$k$$, we can compose these reductions repeatedly to prove $$QBF_k ≤_p SAT$$, where $$SAT$$ is the problem of checking whether a standard quantifier-free propositional formula is satisfiable. Hence $$QBF≤_p SAT$$, since any $$QBF$$ formula has some fixed number of quantified variables.” ?

While this definition of $$SAT$$ is a bit different from the original satisfiability problem (Which requires a CNF, and this may not necessarily be a CNF) I see nothing wrong with the argument? Where am I going wrong?

• The $QBF_k\le_p QBF_{k-1}$ does not even seem to hold if you allow polynomially many (or even non-constantly many) variables in a row to be quantified the same. Commented May 14, 2022 at 22:39
• What do you mean by quantified the same? Could you give an example where the reduction would not hold? Commented May 14, 2022 at 23:06
• Consider $QBF_2$ like $\forall x_1... \forall x_i \exists y_1... \exists y_j: \Phi(x, y)$. Id you could turn it to SAT with at most polynomial size increase, then $PH$ would collapse. But naive reduction would produce $2^i$ formulas on $O(j)$ variables. Commented May 15, 2022 at 7:45
• But that's $QBF_{i+j}$ and not $QBF_{2}$? Commented May 15, 2022 at 8:36
• Not the one that is known, since $PH$ is not known to collapse yet. Commented May 15, 2022 at 10:14

Even though $$QBF_k \le QBF_{k-1}$$, you cannot compose the reductions the way you are doing and still get a polynomial reduction, because you are composing a non-constant number of them.