7
$\begingroup$

We have, from this thread on 3-SAT upper bounds, and this answer on #P that the current best upper bounds for 3-SAT is faster than $O(1.31)^n$, and approximately $O(1.64^n)$ for #3-SAT.

Can we do better for 3-SAT and #3-SAT circuits?

The reason I ask is that I've been fiddling with a circuit that achieves a modest improvement over the #3-SAT upper bounds mentioned above. But since it's a circuit, I have my doubts that it's even worthwhile. So I'm wondering: what kind of circuit upper bounds can we get?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.