<p>I started to read <em>Avi Wigderson</em> book <em><a href="https://www.math.ias.edu/avi/book" rel="nofollow noreferrer">Math and Computation</a></em>, which get me excited about the following:</p>
<blockquote>
<p><strong>Conjecture 5.7.</strong> <span class="math-container">$
S(SAT)=2^{\Omega{(n)}}
$</span>,
where <span class="math-container">$S$</span> denotes the size of the smallest Boolean circuits computing it's input, e.g. <span class="math-container">$SAT$</span> in the conjecture case.</p>
</blockquote>
<p>I didn't find Theorem, Lemma, or anything related to the implication of this conjecture, so my questions are:</p>
<ul>
<li>If <strong>Conjecture 5.7.</strong> is <strong>true</strong>, does it imply <span class="math-container">$P \neq NP$</span>? since its circuits need at least <span class="math-container">$2^{\Omega(n)}$</span> to be constructed, which leads to exponential time algorithm, which means <span class="math-container">$SAT \not\in P$</span>, recalling that <span class="math-container">$P = NP \iff SAT \in P$</span>, right? any other implications? — <em>SEE UPDATE.</em></li>
<li>If <strong>Conjecture 5.7.</strong> is <strong>false</strong>, what its implications?</li>
</ul>
<hr />
<p><strong>UPDATE:</strong> I found the following theorem:</p>
<blockquote>
<p><strong>Theorem 7.7.</strong> If <span class="math-container">$SAT$</span> cannot be solved by circuits of size <span class="math-container">$2^{o(n)}$</span>, then <span class="math-container">$P=BPP$</span>.</p>
</blockquote>
<p>An equivalent and more general result here <a href="https://www.math.ias.edu/%7Eavi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf" rel="nofollow noreferrer">Impagliazzo, Wigderson 1997</a>. If the conjecture is <strong>true</strong> that implies <span class="math-container">$P=BPP$</span>.</p>

CC BY-SA 4.0
2021-05-06T01:34:15.633Z
This is equivalent to the exponential time hypothesis (ETH).
Laakeri
CC BY-SA 4.0
2021-05-06T01:55:34.720Z
@Laakeri: I don't think so. ETH is about (uniform) algorithms, whereas this is about circuits. I would call this "non-uniform ETH."
Huck Bennett
CC BY-SA 4.0
2021-05-06T02:20:01.867Z
@HuckBennett I don't know so much in the literature, but somehow it's looks like ETH related to circuits lower bound, as [this report](https://eccc.weizmann.ac.il/report/2019/169/) say.
Fares
CC BY-SA 4.0
2021-05-06T05:12:02.550Z
@HuckBennett Yes, you are right
Laakeri
CC BY-SA 4.0
2021-05-07T21:28:48.793Z
I think one needs to be a bit careful here in how SAT instances are encoded.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-05-07T22:58:19.853Z
@KristofferArnsfeltHansen Can you illustrate?
Turbo
CC BY-SA 4.0
2021-05-08T05:58:21.960Z
There is a desceptive discrepancy in notation. In the Impagliazzo–Wigderson theorem, $n$ is the size of the input in bits. In contrast, the circuit size of SAT is normally expressed in terms of $n$ being the number of *variables* of the input CNF. There is an upper bound $2^nN^{O(1)}$ on the circuit size of SAT, where $N$ is the bit-size of the input, hence you *cannot* expect it to require circuit size $2^{\Omega(N)}$, unless you consider some severely restricted version of SAT that can be encoded in $N=O(n)$ bits, but somehow still manages to be exponentially hard. This is quite problematic.
Emil Jeřábek
CC BY-SA 4.0
2021-05-08T10:11:09.553Z
To put it differently: assume that CNF are encoded in a standard way (with variable indices written in binary, and $O(1)$-bit polarity indicators and separators). Then an $N$-bit CNF contains at most $N/\log N$ distinct variables, hence SAT is solvable in deterministic time $2^{O(N/\log N)}$, and it has circuits of size $2^{O(N/\log N)}$. Thus, the best you can hope for is that SAT requires circuit size $2^{\Omega(N/\log N)}$. (This *is* likely true: e.g., it follows if satisfiability of 3-CNF with $O(n)$ clauses requires circuit size $2^{\Omega(n)}$.) This is *not* enough to give P = BPP. ...
Emil Jeřábek
CC BY-SA 4.0
2021-05-08T10:21:03.013Z
... It only implies that BPP is solvable in deterministic quasipolynomial time. (More precisely, it implies $\mathrm{BPP\subseteq DTIME}(n^{O(\log\log n)})$, if my back-of-the-virtual-envelope calculation is correct.)
Emil Jeřábek
CC BY-SA 4.0
2021-05-08T10:21:19.033Z
Let me also note that I didn’t read the book, but based on the few pages I’ve seen now, this is not a textbook or a research monograph, but a pop-sci book. (E.g., there are no proofs.) Thus, the author is most likely shaving corners of the exposition so that technical correctness does not stand in the way of getting a good story. You should not take it too literally.
Emil Jeřábek
<cc.complexity-theory>
The implication of $ S(SAT)=2^{\Omega{(n)}} $ Conjecture (5.7 in Wigderson Book)
Fares
# The implication of $ S(SAT)=2^{\Omega{(n)}} $ Conjecture (5.7 in Wigderson Book)

(Asked by: username_0 on 2021-05-05)

I started to read *Avi Wigderson* book *[Math and Computation](https://www.math.ias.edu/avi/book)*, which get me excited about the following:

> **Conjecture 5.7.** $
> S(SAT)=2^{\Omega{(n)}}
> $,
> where $S$ denotes the size of the smallest Boolean circuits computing it's input, e.g. $SAT$ in the conjecture case.

I didn't find Theorem, Lemma, or anything related to the implication of this conjecture, so my questions are:

* If **Conjecture 5.7.** is **true**, does it imply $P \neq NP$? since its circuits need at least $2^{\Omega(n)}$ to be constructed, which leads to exponential time algorithm, which means $SAT \not\in P$, recalling that $P = NP \iff SAT \in P$, right? any other implications? — *SEE UPDATE.*
* If **Conjecture 5.7.** is **false**, what its implications?

---

**UPDATE:** I found the following theorem:

> **Theorem 7.7.** If $SAT$ cannot be solved by circuits of size $2^{o(n)}$, then $P=BPP$.

An equivalent and more general result here [Impagliazzo, Wigderson 1997](https://www.math.ias.edu/%7Eavi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf). If the conjecture is **true** that implies $P=BPP$.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: This is equivalent to the exponential time hypothesis (ETH).  
> **username_2**: @username_1: I don't think so. ETH is about (uniform) algorithms, whereas this is about circuits. I would call this "non-uniform ETH."  
> **username_0**: @HuckBennett I don't know so much in the literature, but somehow it's looks like ETH related to circuits lower bound, as [this report](https://eccc.weizmann.ac.il/report/2019/169/) say.  
> **username_1**: @HuckBennett Yes, you are right  
> **username_3**: I think one needs to be a bit careful here in how SAT instances are encoded.  
> **username_4**: @KristofferArnsfeltHansen Can you illustrate?  
> **username_5**: There is a desceptive discrepancy in notation. In the Impagliazzo–Wigderson theorem, $n$ is the size of the input in bits. In contrast, the circuit size of SAT is normally expressed in terms of $n$ being the number of *variables* of the input CNF. There is an upper bound $2^nN^{O(1)}$ on the circuit size of SAT, where $N$ is the bit-size of the input, hence you *cannot* expect it to require circuit size $2^{\Omega(N)}$, unless you consider some severely restricted version of SAT that can be encoded in $N=O(n)$ bits, but somehow still manages to be exponentially hard. This is quite problematic.  
> **username_5**: To put it differently: assume that CNF are encoded in a standard way (with variable indices written in binary, and $O(1)$-bit polarity indicators and separators). Then an $N$-bit CNF contains at most $N/\log N$ distinct variables, hence SAT is solvable in deterministic time $2^{O(N/\log N)}$, and it has circuits of size $2^{O(N/\log N)}$. Thus, the best you can hope for is that SAT requires circuit size $2^{\Omega(N/\log N)}$. (This *is* likely true: e.g., it follows if satisfiability of 3-CNF with $O(n)$ clauses requires circuit size $2^{\Omega(n)}$.) This is *not* enough to give P = BPP. ...  
> **username_5**: ... It only implies that BPP is solvable in deterministic quasipolynomial time. (More precisely, it implies $\mathrm{BPP\subseteq DTIME}(n^{O(\log\log n)})$, if my back-of-the-virtual-envelope calculation is correct.)  
> **username_5**: Let me also note that I didn’t read the book, but based on the few pages I’ve seen now, this is not a textbook or a research monograph, but a pop-sci book. (E.g., there are no proofs.) Thus, the author is most likely shaving corners of the exposition so that technical correctness does not stand in the way of getting a good story. You should not take it too literally.  

---

## 0 answers

