We clearly know that 2-QCNF is in $\mathsf{P}$. Since that, if I understand it right, it is possible to solve it with #SAT solver (because $\mathsf{P} \subseteq \mathsf{\#P}$). But how can we only knowing amount of positive assignments for some non-quantified formulae solve 2-QCNF? And why this doesn't hold (at least, assumed so) for general case of TQBF?


First of all, it is a bit misleading to say that $\mathsf{P} \subseteq \mathsf{\#P}$, since $\mathsf{P}$ is a class of decision problems, while $\mathsf{\#P}$ is a class of counting problems. However, we can think of a decision problem as a counting problem in which the answer is 0 (no) or 1 (yes), and in that sense it is certainly true that $\mathsf{P} \subseteq \mathsf{\#P}$.

The problem $\mathsf{\#SAT}$ is $\mathsf{\#P}$-complete. This means that for any problem $A \in \mathsf{\#P}$ there exists a polynomial time reduction $f$ such that for any instance $x$ of $A$, we have $$ A(x) = \mathsf{\#SAT}(f(x)), $$ where $A(x)$ is the value of the counting problem $A$ on instance $x$.

Since $\mathsf{2QCNF} \in \mathsf{P}$, there is a trivial reduction from $\mathsf{2QCNF}$ to $\mathsf{\#SAT}$: if the $\mathsf{2QSAT}$ is satisfiable, we output the formula $x$, and otherwise we output the formula $x \land \lnot x$. This reduction runs in polynomial time since $\mathsf{2QCNF} \in \mathsf{P}$.

  • $\begingroup$ But here we solve 2QSAT to convert it to #SAT? Why we even reduce it, if we already know the answer? I thought that's not how reduction works. $\endgroup$ – rus9384 Jun 2 '17 at 17:25
  • $\begingroup$ We can do whatever we want as long as we follow the rules. The reduction I describe satisfies all the requisite properties, so it's a valid reduction. $\endgroup$ – Yuval Filmus Jun 2 '17 at 21:08
  • $\begingroup$ As to why we reduce it, if we already know the answer - it's because you asked for such a reduction. $\endgroup$ – Yuval Filmus Jun 2 '17 at 21:09
  • $\begingroup$ But if we had $\mathsf{NL}^{\mathsf{\#P}}$ machine, that machine should be capable to solve 2QCNF (or not?) but such reduction is restricted. All I know that such machine can solve 2QCNF with zero-error probability, as well as $\mathsf{P}^{\mathsf{\#P}}$ machine can solve TQBF with zero-error probability. $\endgroup$ – rus9384 Jun 2 '17 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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