# Is SAT in $c^{\sqrt{n}}$ time with preprocessing worthwhile?

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.

• Basically, what I'm asking is if SAT is already known to have sub-exponential sized circuits. Mar 29 '14 at 16:17
• While I suppose we could say that SAT is in SUBEXP, we would be wrong. $\:$ See SUBEXP and SE. $\hspace{.25 in}$
– user6973
Mar 29 '14 at 17:37
• @RickyDemer: I fixed the question. Mar 29 '14 at 20:40
• 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. Mar 30 '14 at 4:24