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$.