<p>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 <a href="https://cstheory.stackexchange.com/a/9656/1549">this answer</a>, Ryan Williams points out that we could have a large amount of preprocessing, and SAT in QP (quasi-polynomial) would still be interesting.</p>

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

CC BY-SA 3.0
2014-03-29T16:17:52.867Z
Basically, what I'm asking is if SAT is already known to have sub-exponential sized circuits.
Matt Groff
CC BY-SA 3.0
2014-03-29T20:40:18.830Z
@RickyDemer:  I fixed the question.
Matt Groff
CC BY-SA 3.0
2014-03-30T04:24:40.287Z
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.
Yuval Filmus
<cc.complexity-theory><sat>
Is SAT in $c^{\sqrt{n}}$ time with preprocessing worthwhile?
Matt Groff
# Is SAT in $c^{\sqrt{n}}$ time with preprocessing worthwhile?

(Asked by: username_0 on 2014-03-29)

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](https://cstheory.stackexchange.com/a/9656/1549), 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.**

**Tags:** cc.complexity-theory, sat
> **Comments:**
> **username_0**: Basically, what I'm asking is if SAT is already known to have sub-exponential sized circuits.  
> **username_0**: @RickyDemer:  I fixed the question.  
> **username_1**: 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.  

---

## 0 answers

