<p>I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from <a href="https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf" rel="noreferrer">Cody Murray and Ryan Williams' STOC 2018 paper</a>.</p>

<p>In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit <span class="math-container">$C$</span> on <span class="math-container">$n$</span> variables and the promise that either (a) <span class="math-container">$C$</span> is unsatisfiable, or (b) <span class="math-container">$C$</span> has at least <span class="math-container">$2^n/4$</span> 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. </p>

<p>Ryan has a very nice talk on this thread of work; a recording in two parts is available <a href="https://simons.berkeley.edu/talks/lower-bounds-algorithm-design-i" rel="noreferrer">here</a> and <a href="https://simons.berkeley.edu/talks/clone-lower-bounds-algorithm-design-ii" rel="noreferrer">here</a>.</p>

CC BY-SA 4.0
2019-10-30T00:33:50.223Z
So faster Gap Circuit Unsatisfiability follows from faster CIRCUITSAT?
VS.
CC BY-SA 4.0
2019-10-30T03:14:45.850Z
Yes. You can solve Gap Circuit Unsatisfiability by checking if the input circuit is satisfiable.
Robert Andrews
CC BY-SA 4.0
2019-10-29T16:15:10.280Z
2019-10-29T16:15:10.280Z
Robert Andrews
<ol>
<li><p>What is the best algorithm known for <span class="math-container">$CIRCUIT$</span>-<span class="math-container">$SAT$</span> in <span class="math-container">$n$</span> variables and <span class="math-container">$m$</span> gates?</p></li>
<li><p>What is the consequence if there is an <span class="math-container">$\alpha\in(0,1)$</span> such that <span class="math-container">$CIRCUIT$</span>-<span class="math-container">$SAT$</span> in <span class="math-container">$n$</span> variables and <span class="math-container">$m$</span> gates can be solved in <span class="math-container">$2^{(n-n^\alpha)}poly(nm)$</span> time?</p></li>
</ol>

CC BY-SA 4.0
2019-10-26T08:05:45.440Z
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
CC BY-SA 4.0
2019-10-26T08:42:48.817Z
I was thinking $\frac{2^{O(n)}}{superpoly}$.
VS.
CC BY-SA 4.0
2019-10-26T09:30:40.570Z
$2^n/superpoly$, otherwise $2^{2n}/2^n$ would work...
holf
CC BY-SA 4.0
2019-10-29T02:03:36.670Z
(2) is known to imply circuit lower bounds against NQP due to [Cody Murray and Ryan Williams' STOC 2018 paper](https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf). Ryan has a really nice talk on these kinds of results with recordings [here](https://simons.berkeley.edu/talks/lower-bounds-algorithm-design-i) and [here](https://simons.berkeley.edu/talks/clone-lower-bounds-algorithm-design-ii).
Robert Andrews
CC BY-SA 4.0
2019-10-29T02:06:29.970Z
@RobertAndrews Seems like a good answer!
Huck Bennett
CC BY-SA 4.0
2019-11-06T18:48:03.310Z
Neat question!  I've been looking for others to work with on consequences of faster algorithms for circuit SAT if anyone is interested.  :)
Michael Wehar
<cc.complexity-theory><ds.algorithms><circuit-complexity><sat><big-list>
What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?
VS.
# What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?

(Asked by: username_0 on 2019-10-25)

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?

**Tags:** cc.complexity-theory, ds.algorithms, circuit-complexity, sat, big-list
> **Comments:**
> **username_1**: 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.  
> **username_0**: I was thinking $\frac{2^{O(n)}}{superpoly}$.  
> **username_1**: $2^n/superpoly$, otherwise $2^{2n}/2^n$ would work...  
> **username_2**: (2) is known to imply circuit lower bounds against NQP due to [Cody Murray and Ryan Williams' STOC 2018 paper](https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf). Ryan has a really nice talk on these kinds of results with recordings [here](https://simons.berkeley.edu/talks/lower-bounds-algorithm-design-i) and [here](https://simons.berkeley.edu/talks/clone-lower-bounds-algorithm-design-ii).  
> **username_3**: @RobertAndrews Seems like a good answer!  
> **username_4**: Neat question!  I've been looking for others to work with on consequences of faster algorithms for circuit SAT if anyone is interested.  :)  

---

## 1 answers

### Answer by username_2 on 2019-10-29. Score: 5 | Accepted answer

I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from [Cody Murray and Ryan Williams' STOC 2018 paper](https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf).

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.

Ryan has a very nice talk on this thread of work; a recording in two parts is available [here](https://simons.berkeley.edu/talks/lower-bounds-algorithm-design-i) and [here](https://simons.berkeley.edu/talks/clone-lower-bounds-algorithm-design-ii).

> **Comments:**
> **username_0**: So faster Gap Circuit Unsatisfiability follows from faster CIRCUITSAT?  
> **username_2**: Yes. You can solve Gap Circuit Unsatisfiability by checking if the input circuit is satisfiable.  

---

