What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?
What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates can be solved in $2^{(n-n^\alpha)}poly(nm)$ time?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ For 1, this is not better than SAT with $n$ variables and $m$ clauses so I would say no better than bruteforcing. For 2, $O(n-n^\alpha)=O(n)$ thus it is completely trivial. Just bruteforce... Now, if you mean $2^{o(n)}$ then it will violate SETH. $\endgroup$– holfCommented Oct 26, 2019 at 8:05
-
$\begingroup$ I was thinking $\frac{2^{O(n)}}{superpoly}$. $\endgroup$– VS.Commented Oct 26, 2019 at 8:42
-
$\begingroup$ $2^n/superpoly$, otherwise $2^{2n}/2^n$ would work... $\endgroup$– holfCommented Oct 26, 2019 at 9:30
-
2$\begingroup$ (2) is known to imply circuit lower bounds against NQP due to Cody Murray and Ryan Williams' STOC 2018 paper. Ryan has a really nice talk on these kinds of results with recordings here and here. $\endgroup$– Robert AndrewsCommented Oct 29, 2019 at 2:03
-
$\begingroup$ @RobertAndrews Seems like a good answer! $\endgroup$– Huck BennettCommented Oct 29, 2019 at 2:06
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
I'm not sure how to answer (1), but (2) is known to imply circuit lower bounds against NQP (non-deterministic quasi-polynomial time). This is from Cody Murray and Ryan Williams' STOC 2018 paper.
In fact, they show that these lower bounds follow from faster algorithms for what they call Gap Circuit Unsatisfiability: given a circuit $C$ on $n$ variables and the promise that either (a) $C$ is unsatisfiable, or (b) $C$ has at least $2^n/4$ satisfying assignments, determine which of (a) and (b) is the case. This problem is easily solved with randomness, so this hypothesis is perhaps more likely than a faster algorithm for Circuit Satisfiability.
Ryan has a very nice talk on this thread of work; a recording in two parts is available here and here.
-
1$\begingroup$ So faster Gap Circuit Unsatisfiability follows from faster CIRCUITSAT? $\endgroup$– VS.Commented Oct 30, 2019 at 0:33
-
1$\begingroup$ Yes. You can solve Gap Circuit Unsatisfiability by checking if the input circuit is satisfiable. $\endgroup$ Commented Oct 30, 2019 at 3:14