# Complexity of All-SAT

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.

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$$.
• So this would mean that All-SAT $\in$ #P? Apr 30 at 9:48
• 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. Apr 30 at 9:53