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

$\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$ 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$ 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$ 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$ May 8, 2021 at 10:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.