We may be able to solve SAT in $c^{\sqrt{n}}$ for $n$ variables and a constant $c$. Now we can suppose that we require a certain amount of preprocessing to get this result. For example, in this answer, Ryan Williams points out that we could have a large amount of preprocessing, and SAT in QP (quasi-polynomial) would still be interesting.

So my question is, if we solve SAT in $c^{\sqrt{n}}$, how much preprocessing can we have and still have an interesting result? In other words, if we had something like $2^{2^n}$ preprocessing, would this remain an interesting result? Basically, we would be saying that SAT has $c^{\sqrt{n}}$ sized circuits.

  • $\begingroup$ Basically, what I'm asking is if SAT is already known to have sub-exponential sized circuits. $\endgroup$
    – Matt Groff
    Commented Mar 29, 2014 at 16:17
  • $\begingroup$ While I suppose we could say that SAT is in SUBEXP, we would be wrong. $\:$ See SUBEXP and SE. $\hspace{.25 in}$ $\endgroup$
    – user6973
    Commented Mar 29, 2014 at 17:37
  • $\begingroup$ @RickyDemer: I fixed the question. $\endgroup$
    – Matt Groff
    Commented Mar 29, 2014 at 20:40
  • 4
    $\begingroup$ It is conjectured that SAT doesn't have subexponential size circuits (which implies P=BPP), so this will be interesting for an arbitrary preprocessing time. $\endgroup$ Commented Mar 30, 2014 at 4:24


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.