<p>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:</p>

<p><strong>Problem.</strong> 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$.</p>

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

<p>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.)</p>

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

CC BY-SA 3.0
2012-09-23T20:16:22.947Z
2012-09-23T20:16:22.947Z
D.W.
<p>If what you are studying worked out, it definitely would not be trivial.</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-01-07T19:31:43.943Z
: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
CC BY-SA 3.0
2012-01-07T20:07:56.017Z
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
CC BY-SA 3.0
2012-01-13T06:03:18.617Z
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
CC BY-SA 3.0
2012-01-14T06:15:15.393Z
@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
CC BY-SA 3.0
2012-01-07T18:54:56.603Z
2012-01-07T18:54:56.603Z
Ryan Williams
<p>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.</p>

<p>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.</p>

<p>I'm thinking that the bounds itself beats the upper bounds presented in <a href="https://cstheory.stackexchange.com/questions/1060">this question</a> (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?</p>

<p>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.</p>

<hr>

<p><strong>UPDATE</strong></p>

<p>I have been studying related problems in addition to researching this algorithm.  I asked <a href="https://security.stackexchange.com/questions/20585/how-will-security-need-to-be-changed-if-we-can-crack-password-hashes-in-quasi-po">This question on StackExchange's IT Security site</a> relating to password cracking and SAT, if you are interested.  At least one of the answers reflects this.</p>

CC BY-SA 3.0
2012-01-07T20:33:23.993Z
You say it takes O(N^2+logc) time/space... So it is not in PSPACE? But in QSPACE (Quasi-Space)?
Tayfun Pay
CC BY-SA 3.0
2012-01-07T22:12:52.913Z
@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
CC BY-SA 3.0
2012-01-07T23:13:17.793Z
Does it need O(N^(2+log(c))) SPACE?
Tayfun Pay
CC BY-SA 3.0
2012-01-07T23:49:54.567Z
@Tayfun Pay: Yes.  I haven't found a way to reduce the space considerations yet.
Matt Groff
CC BY-SA 3.0
2012-01-08T03:27:42.493Z
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
CC BY-SA 3.0
2012-01-08T15:32:05.230Z
@Yoshio Okamoto: Done.  I hope that the new title is much more suitable.
Matt Groff
CC BY-SA 3.0
2012-01-09T08:36:28.567Z
@MattGroff: Thanks. Would you make it more explicit what you mean by "a result modulo a prime p"? Does your algorithm count the number of satisfying assignments modulo p, or do something else? I'm not sure what problem your algorithm is solving.
Yoshio Okamoto
CC BY-SA 3.0
2012-01-09T19:43:03.550Z
My algorithm counts the number of satisfying assignments modulo $p$.  Thus, there is a problem if the number of satisfying assignments is equivalent to $0 \bmod p$.  However, as Ryan Williams has pointed out to me that there is a way around some problems that this creates.  Using the Valiant-Vazirani lemma, there is a randomized polynomial time reduction that may come in handy.  It looks to me that it can produce equivalent problems that have only one satisfying solution, and thus the problems with arbitrary $p$ may be resolved.
Matt Groff
CC BY-SA 3.0
2012-09-24T16:53:51.820Z
@Matt Thanks I will read the answer to that question tonight.
Tayfun Pay
<ds.algorithms><sat><upper-bounds>
Are quasi-polynomial sized circuits for 3-SAT trivial?
Matt Groff
# Are quasi-polynomial sized circuits for 3-SAT trivial?

(Asked by: username_0 on 2012-01-07)

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](https://cstheory.stackexchange.com/questions/1060) (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](https://security.stackexchange.com/questions/20585/how-will-security-need-to-be-changed-if-we-can-crack-password-hashes-in-quasi-po) relating to password cracking and SAT, if you are interested. At least one of the answers reflects this.

**Tags:** ds.algorithms, sat, upper-bounds

> **Comments:**
> **username_1**: You say it takes O(N^2+logc) time/space... So it is not in PSPACE? But in QSPACE (Quasi-Space)?  
> **username_0**: @username_1:  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$.  
> **username_1**: Does it need O(N^(2+log(c))) SPACE?  
> **username_0**: @username_1: Yes.  I haven't found a way to reduce the space considerations yet.  
> **username_2**: 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.  
> **username_0**: @username_2: Done.  I hope that the new title is much more suitable.  
> **username_2**: @MattGroff: Thanks. Would you make it more explicit what you mean by "a result modulo a prime p"? Does your algorithm count the number of satisfying assignments modulo p, or do something else? I'm not sure what problem your algorithm is solving.  
> **username_0**: My algorithm counts the number of satisfying assignments modulo $p$.  Thus, there is a problem if the number of satisfying assignments is equivalent to $0 \bmod p$.  However, as username_4 has pointed out to me that there is a way around some problems that this creates.  Using the Valiant-Vazirani lemma, there is a randomized polynomial time reduction that may come in handy.  It looks to me that it can produce equivalent problems that have only one satisfying solution, and thus the problems with arbitrary $p$ may be resolved.  
> **username_1**: @Matt Thanks I will read the answer to that question tonight.  

---

## 2 answers

### Answer by username_4 on 2012-01-07. Score: 17 | Accepted answer

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?

> **Comments:**
> **username_0**: :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.  
> **username_4**: 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.  
> **username_5**: 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?  
> **username_4**: @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.  

---

### Answer by username_3 on 2012-09-23. Score: 3

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.


---

