HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
satwhycanqbfreduced

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#151554, answer score: 6

Revisions (0)

No revisions yet.