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.

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.