2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Basically, what I'm asking is if SAT is already known to have sub-exponential sized circuits. $\endgroup$ – Matt Groff Mar 29 '14 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 Mar 29 '14 at 17:37
  • $\begingroup$ @RickyDemer: I fixed the question. $\endgroup$ – Matt Groff Mar 29 '14 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$ – Yuval Filmus Mar 30 '14 at 4:24

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.