<p><a href="https://web.stanford.edu/~rrwill/ICM-survey.pdf" rel="nofollow">Williams</a> (see also slide 29 <a href="http://cseweb.ucsd.edu/~slovett/workshops/socal-theory-day-2014/williams-talk.pdf" rel="nofollow">here</a>) has shown that an $\frac{2^{n}}{n^{10}}$ algorithm for satisfiability of circuits belonging to a class $\mathcal{C}$ imply that $\mathrm{NEXP}\nsubseteq \mathcal{C}$.</p>

<p>What are the consequences of an algorithm running in time $2^{o(n)}$ for satisfiability of circuits on class $\mathcal{C}$? Would this imply that some smaller class, such as $\mathrm{EXP}$ is not included in $\mathcal{C}$? What would be the smallest class which would be separated from $\mathcal{C}$ by such a faster algorithm? </p>

<p>Obs1: $n$ is the number of variables.</p>

<p>Obs2: I'm mostly interested in the case in which $\mathcal{C}=\mathrm{NC}^1$</p>

<p>See also the following references: </p>

<p>1) Williams, Improving Exhaustive Search Implies Superpolynomial Lower Bounds, 2010</p>

<p>2) Williams, Algorithms for circuits and circuits for algorithms, 2014</p>

CC BY-SA 3.0
2016-09-17T12:12:57.427Z
@RickyDemer $n$ is the number of variables. The claim as stated in the question is made at slide 29 of ref 2.
Parachutes
CC BY-SA 3.0
2016-09-18T02:39:33.667Z
Please edit the question to include all relevant information in the question.  Don't just leave information in the comments; we want questions to stand on their own, so people don't have to read the comments to understand what you are asking.  Also, please proof-read your question: something seems to have gone wrong with some of the Markdown.  Finally, it's helpful to give a full reference for those papers (with title, authors, and where published), so the question is still understandable even if the link stops working, and so others with a similar question can find this by search.  Thank you!
D.W.
CC BY-SA 3.0
2016-09-18T21:49:48.430Z
The above comment is important because the answer depends on the class C. See the paper "Improving exhaustive search implies superpolynomial lower bounds" for the best answer that I know.
Ryan Williams
CC BY-SA 3.0
2016-09-20T18:36:48.837Z
@RyanWilliams Thanks for the paper. I'm mostly interested in the case in which $\mathcal{C} = NC^1$.
Parachutes
<complexity-classes><circuit-complexity><sat>
Subexponential algorithms vs separations
Parachutes
# Subexponential algorithms vs separations

(Asked by: username_0 on 2016-09-17)

[Williams](https://web.stanford.edu/~rrwill/ICM-survey.pdf) (see also slide 29 [here](http://cseweb.ucsd.edu/~slovett/workshops/socal-theory-day-2014/williams-talk.pdf)) has shown that an $\frac{2^{n}}{n^{10}}$ algorithm for satisfiability of circuits belonging to a class $\mathcal{C}$ imply that $\mathrm{NEXP}\nsubseteq \mathcal{C}$.

What are the consequences of an algorithm running in time $2^{o(n)}$ for satisfiability of circuits on class $\mathcal{C}$? Would this imply that some smaller class, such as $\mathrm{EXP}$ is not included in $\mathcal{C}$? What would be the smallest class which would be separated from $\mathcal{C}$ by such a faster algorithm?

Obs1: $n$ is the number of variables.

Obs2: I'm mostly interested in the case in which $\mathcal{C}=\mathrm{NC}^1$

See also the following references:

1) Williams, Improving Exhaustive Search Implies Superpolynomial Lower Bounds, 2010

2) Williams, Algorithms for circuits and circuits for algorithms, 2014

**Tags:** complexity-classes, circuit-complexity, sat

> **Comments:**
> **username_0**: @RickyDemer $n$ is the number of variables. The claim as stated in the question is made at slide 29 of ref 2.  
> **username_1**: Please edit the question to include all relevant information in the question.  Don't just leave information in the comments; we want questions to stand on their own, so people don't have to read the comments to understand what you are asking.  Also, please proof-read your question: something seems to have gone wrong with some of the Markdown.  Finally, it's helpful to give a full reference for those papers (with title, authors, and where published), so the question is still understandable even if the link stops working, and so others with a similar question can find this by search.  Thank you!  
> **username_2**: The above comment is important because the answer depends on the class C. See the paper "Improving exhaustive search implies superpolynomial lower bounds" for the best answer that I know.  
> **username_0**: @RyanWilliams Thanks for the paper. I'm mostly interested in the case in which $\mathcal{C} = NC^1$.  

---

## 0 answers

