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$

0

Your Answer

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

Browse other questions tagged or ask your own question.