# The implication of $S(SAT)=2^{\Omega{(n)}}$ Conjecture (5.7 in Wigderson Book)

I started to read Avi Wigderson book Math and Computation, 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. If the conjecture is true that implies $$P=BPP$$.

• @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 May 6 at 1:55
• I think one needs to be a bit careful here in how SAT instances are encoded. – Kristoffer Arnsfelt Hansen May 7 at 21:28
• @KristofferArnsfeltHansen Can you illustrate? – 1.. May 7 at 22:58
• 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 May 8 at 5:58
• 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 May 8 at 10:11