1
$\begingroup$

All-SAT is the problem of enumerating all satisfying assignments of a boolean formula.

All-SAT is different from #SAT, where it suffices to find the number of satisfying assignments without enumerating them.

Is the computational complexity of All-SAT known, or is this an open problem?

In this CS Theory question, some solvers for All-SAT are discussed, but the papers do not seem to give complexity results.

$\endgroup$
3
$\begingroup$

You can naively compute ALL-SAT in $2^npoly(n,m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. You clearly need $\Omega(2^n)$ time in the worst case just to write down the assignments (in the case of a tautology). If the strong exponential time hypothesis (SETH) holds, then this is not much harder than SAT itself, so under SETH the complexity of SAT, ALL-SAT, #SAT is the same (up to polynomial factors).

Moreover, without SETH you can claim that given access to a $\#SAT$ oracle, you can output all satisfying assignments in time $k(\varphi)poly(n,m)$ where $k(\varphi)$ is the number of satisfying assignments for $\varphi$ (just see if the number of satisfying assignments changes when substituting $1$ or $0$ to some variable $x_i$). This also shows that in some sense ALL-SAT is not much harder than $\#SAT$.

$\endgroup$
3
  • $\begingroup$ Awesome, thank you! $\endgroup$ – mto_19 Apr 30 at 9:43
  • $\begingroup$ So this would mean that All-SAT $\in$ #P? $\endgroup$ – mto_19 Apr 30 at 9:48
  • 1
    $\begingroup$ Well $\#P$ contains objects of a different type, so I wouldn't say that. You could treat the output of ALL-SAT as a natural number (encode the list of satisfying assignments) and then ask if this function can be described as the counter of some NP-machine. The membership to $\#P$ now might depend on the details of the encoding, but I don't suspect there is anything too deep here. My point was that they admit to the same lower bounds, and if you had a SAT or $\#SAT$ oracle you would obtain a near optimal solution for ALL-SAT. $\endgroup$ – Ariel Apr 30 at 9:53

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.