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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.