11
$\begingroup$

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.

UPDATE

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ You say it takes O(N^2+logc) time/space... So it is not in PSPACE? But in QSPACE (Quasi-Space)? $\endgroup$
    – Tayfun Pay
    Jan 7, 2012 at 20:33
  • $\begingroup$ @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$. $\endgroup$
    – Matt Groff
    Jan 7, 2012 at 22:12
  • $\begingroup$ Does it need O(N^(2+log(c))) SPACE? $\endgroup$
    – Tayfun Pay
    Jan 7, 2012 at 23:13
  • $\begingroup$ @Tayfun Pay: Yes. I haven't found a way to reduce the space considerations yet. $\endgroup$
    – Matt Groff
    Jan 7, 2012 at 23:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yoshio Okamoto
    Jan 8, 2012 at 3:27

2 Answers 2

Reset to default
17
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ :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. $\endgroup$
    – Matt Groff
    Jan 7, 2012 at 19:31
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Jan 7, 2012 at 20:07
  • 2
    $\begingroup$ 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. $\;\;$ $\endgroup$
    – user6973
    Jan 7, 2012 at 22:34
  • $\begingroup$ 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? $\endgroup$
    – Zirui Wang
    Jan 13, 2012 at 6:03
  • $\begingroup$ @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. $\endgroup$
    – Ryan Williams
    Jan 14, 2012 at 6:15
3
$\begingroup$

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.

Improve this answer
$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.