2
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 8
    $\begingroup$ @Laakeri: I don't think so. ETH is about (uniform) algorithms, whereas this is about circuits. I would call this "non-uniform ETH." $\endgroup$ – Huck Bennett May 6 at 1:55
  • 2
    $\begingroup$ I think one needs to be a bit careful here in how SAT instances are encoded. $\endgroup$ – Kristoffer Arnsfelt Hansen May 7 at 21:28
  • 1
    $\begingroup$ @KristofferArnsfeltHansen Can you illustrate? $\endgroup$ – 1.. May 7 at 22:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek May 8 at 5:58
  • 1
    $\begingroup$ 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. ... $\endgroup$ – Emil Jeřábek May 8 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.