Take the 2-minute tour ×

Suppose we consider 3-SAT with $v$ variables and $c$ clauses. I am researching a method that appears to take $O(v^{2+\log c})$ time/space to solve any SAT problem fitting this description, to within an error that can be adjusted to an arbitrary amount. However, there is a catch.

This method requires a set of precomputed values, after which it can solve an arbitrary 3-SAT problem fitting the above description. The precomputed values are a set of size $O(v^{2+\log c})$ with each value taking $O(1)$ space. The real problem is that each of these values could take $O(2^v)$ time to compute. There is a chance that I can find a way to speed up these calculations.

I'm thinking that the bounds itself beats the upper bounds presented in this question (for small $c$). So I'm wondering, is there a trivial way to reach the upper bounds I describe if we allow $O(v^{2+\log c})$ precomputations?

I'd like to continue this research and hopefully publish my results if everything works out, but first I'd like to know if there is a trivial way to do as well or better.


I have been studying related problems in addition to researching this algorithm. I asked This question on StackExchange's IT Security site relating to password cracking and SAT, if you are interested. At least one of the answers reflects this.

share|improve this question
You say it takes O(N^2+logc) time/space... So it is not in PSPACE? But in QSPACE (Quasi-Space)? –  Tayfun Pay Jan 7 '12 at 20:33
@Tayfun Pay: It runs in $O(v^{(2+\log c)})$. It is a deterministic algorithm that gives a result modulo a prime $p$ (note that this result is enough for the rest of the algorithm to determine a satisfying assignment). It can be run for any prime. Running for more than one prime increases its chance of finding a satisfying assignment. It has a chance of finding a satisfying assignment, if one exists, of $(p-1)/p$. –  Matt Groff Jan 7 '12 at 22:12
Does it need O(N^(2+log(c))) SPACE? –  Tayfun Pay Jan 7 '12 at 23:13
@Tayfun Pay: Yes. I haven't found a way to reduce the space considerations yet. –  Matt Groff Jan 7 '12 at 23:49
I would propose to change the title to an more appropriate one. The current title doesn't look appealing, while the question itself looks so. –  Yoshio Okamoto Jan 8 '12 at 3:27

2 Answers 2

up vote 16 down vote accepted

If what you are studying worked out, it definitely would not be trivial.

It would imply that 3SAT has (non-uniform) circuits of size $n^{O(\log n)}$. Then, every language in $NP$ (and the polynomial time hierarchy) would have quasi-polynomial (i.e., $n^{O(\log^c n)}$) size circuits.

Even if it took $2^{2^n}$ preprocessing time to produce a data structure of size only $2^{O(\log^2 n)}$ which could then correctly answer arbitrary 3SAT queries of size $n$ in $2^{O(\log^2 n)}$ randomized time with high probability, 3SAT would have quasi-polynomial size circuits, using the known translation of randomized algorithms to circuits. This would not improve the known algorithm time bounds because of the preprocessing, but it would still be extremely interesting as a non-uniform result.

What do you mean by "to within an error that can be adjusted to an arbitrary amount"? Is the algorithm randomized?

share|improve this answer
:Thanks for your answer. The algorithm is not randomized. The actual running time of the algorithm itself is not quite as simple as I described it. Basically put, though, we can run it through repeated runs to eliminate error. So if we run it through $x$ times, the probability of error would be reduced below $1/(2^x)$. I hesistate to give away the details because I'm worried that it will reveal too much about the algorithm. –  Matt Groff Jan 7 '12 at 19:31
How can the algorithm not be randomized, yet you can run it repeatedly to reduce error? I think that you would probably have to give at least a few more details, in order to understand your question. –  Ryan Williams Jan 7 '12 at 20:07
His algorithm is such that (if it works), for each prime $p$, if the number of satisfying assignments is not a multiple of $p$ then the algorithm finds a satisfying assignment. $\;$ He is (wrongly) referring to that as "a change of finding a satisfying assignment, if one exists, of $(p-1)/p$." $\hspace{0.9 in}$ If the runtime's dependency on $p$ is not huge, then this yields (deterministic) quasi-polynomial sized circuits for SAT. $\;\;$ –  Ricky Demer Jan 7 '12 at 22:34
The preprocessing step needs $p$. Can I have a reference to "the known translation of randomized algorithms to circuits"? So if you want to reduce error, you have to run preprocessing $n$ times. I doubt this can be translated to a quasi circuit. What advantage will this have over a trivial algorithm? –  Zirui Wang Jan 13 '12 at 6:03
@ZiruiWang: Look up $BPP \subset P/poly$. Suppose the data structure answers queries correctly with probability $3/4$. Take $100n$ copies of the data structure of size $2^{O(\log^2 n)}$ each seeded with different strings of random bits. Take the majority answer of all the copies. This is a quasipolynomial time randomized algorithm with error less than $1/2^n$. This can be converted to a quasipolynomial size circuit by hardcoding an appropriate seed. –  Ryan Williams Jan 14 '12 at 6:15

I don't know whether your result -- if valid -- would be a non-trivial advance, but here is one sort of problem you could test it on:

Problem. Fix a function $f:\{0,1\}^n \to \{0,1\}^n$. Given $y \in \{0,1\}^n$, find $x \in \{0,1\}^n$ such that $f(x)=y$.

If $f$ can be computed efficiently (say, by a small circuit), your result implies some sort of solution to this problem.

In the cryptographic world, the best known algorithm for this problem does a precomputation (depending only upon $f$) that requires $2^n$ time and $2^{2n/3}$ space, and outputs some advice of size $2^{2n/3}$; then, given $x$, it can find $y$ in $2^{2n/3}$ time, using the advice string of size $2^{2n/3}$ from the precomputation. You can adjust the space vs time tradeoff, to use an advice string of size $S$ and take time $T$, as long as $S \sqrt{T} = 2^n$. As far as I know, this complexity is believed to be the best possible, for algorithms that do not take into account any of the internal structure of $f$. In particular, it is likely to be optimal when $f$ is a cryptographically secure hash function. (This technique is known as the Hellman time-space tradeoff.)

So, if your technique can do better than the Hellman time-space tradeoff on some cryptographically secure $f$, it would certainly be news.

share|improve this answer

Your Answer


