3
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – rus9384
    May 14, 2022 at 22:39
  • $\begingroup$ What do you mean by quantified the same? Could you give an example where the reduction would not hold? $\endgroup$ May 14, 2022 at 23:06
  • $\begingroup$ 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. $\endgroup$
    – rus9384
    May 15, 2022 at 7:45
  • $\begingroup$ But that's $QBF_{i+j}$ and not $QBF_{2}$? $\endgroup$ May 15, 2022 at 8:36
  • 1
    $\begingroup$ Not the one that is known, since $PH$ is not known to collapse yet. $\endgroup$
    – rus9384
    May 15, 2022 at 10:14

1 Answer 1

6
$\begingroup$

The problem is that the resulting formula does not have a length that is polynomial in the original formula since you are doubling the size of the formula every time you remove a quantifier.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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