# What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?

1. What is the best algorithm known for $$CIRCUIT$$-$$SAT$$ in $$n$$ variables and $$m$$ gates?

2. What is the consequence if there is an $$\alpha\in(0,1)$$ such that $$CIRCUIT$$-$$SAT$$ in $$n$$ variables and $$m$$ gates can be solved in $$2^{(n-n^\alpha)}poly(nm)$$ time?

• For 1, this is not better than SAT with $n$ variables and $m$ clauses so I would say no better than bruteforcing. For 2, $O(n-n^\alpha)=O(n)$ thus it is completely trivial. Just bruteforce... Now, if you mean $2^{o(n)}$ then it will violate SETH. – holf Oct 26 at 8:05
• I was thinking $\frac{2^{O(n)}}{superpoly}$. – VS. Oct 26 at 8:42
• $2^n/superpoly$, otherwise $2^{2n}/2^n$ would work... – holf Oct 26 at 9:30
• (2) is known to imply circuit lower bounds against NQP due to Cody Murray and Ryan Williams' STOC 2018 paper. Ryan has a really nice talk on these kinds of results with recordings here and here. – Robert Andrews Oct 29 at 2:03
• @RobertAndrews Seems like a good answer! – Huck Bennett Oct 29 at 2:06

In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit $$C$$ on $$n$$ variables and the promise that either (a) $$C$$ is unsatisfiable, or (b) $$C$$ has at least $$2^n/4$$ satisfying assignments, determine which of (a) and (b) is the case. This problem is easily solved with randomness, so this hypothesis is perhaps more likely than a faster algorithm for Circuit Satisfiability.