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, 2021 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, 2021 at 21:28
  • 1
    $\begingroup$ @KristofferArnsfeltHansen Can you illustrate? $\endgroup$
    – Turbo
    May 7, 2021 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, 2021 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, 2021 at 10:11

0

Reset to default

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.