5
$\begingroup$
  1. What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?

  2. 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?

$\endgroup$
  • $\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$ – holf Oct 26 at 8:05
  • $\begingroup$ I was thinking $\frac{2^{O(n)}}{superpoly}$. $\endgroup$ – VS. Oct 26 at 8:42
  • $\begingroup$ $2^n/superpoly$, otherwise $2^{2n}/2^n$ would work... $\endgroup$ – holf Oct 26 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 Andrews Oct 29 at 2:03
  • $\begingroup$ @RobertAndrews Seems like a good answer! $\endgroup$ – Huck Bennett Oct 29 at 2:06
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ So faster Gap Circuit Unsatisfiability follows from faster CIRCUITSAT? $\endgroup$ – VS. Oct 30 at 0:33
  • 1
    $\begingroup$ Yes. You can solve Gap Circuit Unsatisfiability by checking if the input circuit is satisfiable. $\endgroup$ – Robert Andrews Oct 30 at 3:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.