<p>It's not quite the same as "every algorithm", but in SODA'04 Achlioptas Beame and Molloy suggested that every backtracking algorithm should require exponential time on random 3SAT instances with $n$ variables and $cn$ clauses, with $c$ chosen within a range of values near the satisfiability threshold.</p>

CC BY-SA 3.0
2012-12-06T05:09:57.127Z
Thank you. Is there a reason they don't conjecture the stronger statement that random k-SAT restricted to clause ratio close to satisfiability threshold is exponentially hard?
Anonymous
CC BY-SA 3.0
2012-12-06T06:28:24.163Z
My guess is that it's because they can prove results about backtracking algorithms that are not conditional on P≠NP.
David Eppstein
CC BY-SA 3.0
2012-12-05T21:56:58.963Z
2012-12-05T23:48:00.683Z
2012-12-05T23:48:00.683Z
David Eppstein
<p>There are several psuedorandom number generators that we have no polynomial time algorithms for breaking. I guess you could consider them to be hard on average cases. Check out the generators at www.ecrypt.eu.org/stream/  There are others of course, you can research most of them online.</p>

CC BY-SA 3.0
2012-12-05T06:48:38.290Z
Is there any particular polytime PRNG that is conjectured to be exponentially hard on average?
Anonymous
CC BY-SA 3.0
2012-12-05T07:39:21.287Z
The Alternating Step Generator invented by Gunther is a beauty for several reasons. It takes two linear feedback shift registers(LFSR's) A & B and XOR's the outputs but the clocking of the two registers is controlled by a third LFSR(C) such that the outputs of A & B enter the XOR gate in an irregular manner. Becuase the bits of C only control the clocking of A & B and do not appear in the output stream, C can be considered a quasi hidden variable that breaks up the inherent linearity of A & B. This is a simplified explanation but you will want to see the circuit for yourself.
William Hird
CC BY-SA 3.0
2012-12-05T09:05:38.400Z
I am not familiar with "Alternating Step Generator invented by Gunther". Is it conjectured to be exponentially hard on average?
Anonymous
CC BY-SA 3.0
2012-12-05T09:15:27.963Z
I don't know how to answer your comment as posed, but the ASG is considered to be unbreakable as long as the key lengths for the three shift registers are around 128 bits each. If this equates to being "exponentially hard on average" then I guess your answer is yes.
William Hird
CC BY-SA 3.0
2012-12-05T09:39:06.777Z
Hard to break in practice usually corresponds to polynomial hardness, not exponential hardness.
Anonymous
CC BY-SA 3.0
2012-12-05T12:02:56.707Z
@Anonnymous: I don't know why you say that. The best algorithsm for RSA and Diffie-Hellman are both superpolynomial (although not exponential), and most good cryptosystems are believed to be asymptotically harder to break than these.
Peter Shor 
CC BY-SA 3.0
2012-12-05T14:15:17.950Z
@Anonymous: Of course the "bare-bones" ASG can be made harder to break by using three ASG's as registers A B & C for another ASG, Gunther alludes to this in his original paper. It's like adding more rounds to a block cipher. How far one can amplify hardness by this method is an open question ( and interesting) :-)
William Hird
CC BY-SA 3.0
2012-12-05T19:15:14.103Z
Peter Shor, it should have been "superpolinomally hard". Are any of these cryptographic problems conjectured to be exponentially hard?
Anonymous
CC BY-SA 3.0
2015-12-06T20:16:13.343Z
One could use communication complexity to analyze the complexity of breaking the ASG because the random clocking of the output registers causes them to have random ( or psuedorandom if you want to be picky) repeats , the same bit from one register is XOR'd with different bits from the other output register. So you can model each output register as being passed through a "sticky"channel. So you have one sticky channel performing a permutation on another sticky channel via the XOR function, that's pretty complex!
William Hird
CC BY-SA 3.0
2012-12-05T02:13:47.467Z
2012-12-05T02:13:47.467Z
William Hird
<p>my understanding is that while there are some candidates from the theory of unbreakability of cryptography and random number generators [eg some cited in Razborov/Rudich, Natural Proofs], most aspects of your question are acknowledged as basically key "still open" questions by experts in the field. from the introduction to the comprehensive survey, <a href="http://rads.stackoverflow.com/amzn/click/1933019492" rel="nofollow"><em>Average Case Complexity</em></a> by Bogdanov and Trevisan (2006) has some related points. Trevisan's <a href="http://www.youtube.com/watch?v=Yo-naUur464" rel="nofollow">youtube lecture on findings and open questions of average case complexity</a> may also be helpful.</p>

<blockquote>
  <p>Applying the theory to natural
  distributional problems remain an outstanding open question.<br>
  ...<br>
  A major open question is whether the existence of hard-on-average
  problems in NP can be based on the P$\neq$NP assumption or on related
  worst-case assumptions. We review negative results showing that certain
  proof techniques cannot prove such a result.<br>
  ...<br>
  In particular, a long-standing open question is whether it is possible
  to base the existence of one-way functions on the P$\neq$NP assumption,
  or related ones (such as NP-complete problems not allowing polynomial
  size circuits).<br>
  ...<br>
  The right techniques to apply such a theory to natural problems and
  distributions have not been discovered yet. From this point of view, the
  current state of the theory of average-case complexity in NP is similar
  to the state of the theory of inapproximability of NP optimization
  problems before the PCP Theorem.</p>
</blockquote>

CC BY-SA 3.0
2012-12-05T19:13:10.303Z
Not an answer to my question. I thought I have explained to you that I am not looking for general commentary on related issues, I am looking for *candidate problems conjectured to be hard*.
Anonymous
CC BY-SA 3.0
2012-12-05T19:20:10.600Z
_whatever!_ imho "the theory does not have a substantial answer to your question at this point in time" along with some of the best/nearest avail refs/authorities on the subj is a legitimate answer to your question, which was posted not merely for _you_
vzn
CC BY-SA 3.0
2012-12-05T19:26:00.950Z
@Anonymous, I am still a bit confused about your meaning of "conjectured". We all may have our personal conjectures, so it's not clear if you're looking for a personal opinion, a stance on an open question that is shared by many people in research, or something in between. It may help to give a more precise statement of what you're looking for. Also, I find answers such as vzn's to be instructive and informative even if they do not relate head-on to your exact question, so I don't see that such answers should be so strongly discouraged.
usul
CC BY-SA 3.0
2012-12-05T19:26:51.157Z
my understanding, it is _widely conjectured that such problems exist with some candidates_ via the one-way function theory but nailing down the details is apparently at least as hard or harder than resolving P$\neq$NP, partly due to subtleties in finding precise math definitions, and not coincidentally because its apparently tightly coupled to that same _conjecture_
vzn
CC BY-SA 3.0
2012-12-05T19:38:49.830Z
moreover as in P.Shor's comment, there is possibly more conjecture about some problems being only _superpolynomial_ in their hardness... basically all conjectured-secure cryptosystems and random number generators (and they are all at this point _conjectured_ to be secure) are (at least implicitly but possibly not directly) conjectured to be of at least superpolynomial hardness....
vzn
CC BY-SA 3.0
2012-12-05T19:46:47.217Z
If you have read my comment to which Peter Shor replied I am already aware of cryptographic problems that are conjectured to be superpolynomially hard. Please read the question carefully, I am not looking for superpolynomially hard problems, I am looking for exponentially hard ones.
Anonymous
CC BY-SA 3.0
2012-12-05T19:48:56.887Z
obviously every problem that is at least superpolynomially hard is also a _candidate_ for an exponentially hard one so perhaps you already knew the answer to your own question before asking =)
vzn
CC BY-SA 3.0
2012-12-05T19:49:54.217Z
usul, by "conjectured" I mean a "mathematical conjecture" as the term is used in mathematical literature: Goldbach's conjecture, unique games conjecture, P is not equal to NP conjecture, etc.
Anonymous
CC BY-SA 3.0
2012-12-05T19:50:39.877Z
vzn, what you wrote is obviously false.
Anonymous
CC BY-SA 3.0
2012-12-05T21:30:15.900Z
Please take further discussion to chat.
Jeffε
CC BY-SA 3.0
2012-12-05T18:21:05.657Z
2012-12-05T18:21:05.657Z
vzn
<p>It might be conjectured that the Learning Parity with Noise Problem (LPN) at constant error rate requires time $2^{n^{1-o(1)}}$.  The fastest known algorithm (Blum-Kalai-Wasserman) uses time $2^{O(n/\log n)}$.</p>

CC BY-SA 3.0
2012-12-05T19:26:21.967Z
Thank you. Could you please give references where I can read more about the LPN problem?
Anonymous
CC BY-SA 3.0
2012-12-05T21:19:05.447Z
@Anonymous:  This paper states several conjectures on the hardness of LPN: M. Alekhnovich. “More on Average Case vs Approximation Complexity.” In Proc. of the 44th Symposium on Foundations of Computer Science, pp, 298—307, 2003.
Yury
CC BY-SA 3.0
2012-12-06T05:04:08.440Z
Yury, thanks for the reference: http://www.math.ias.edu/~misha/papers/average.ps
Anonymous
CC BY-SA 3.0
2012-12-05T18:34:53.953Z
2012-12-05T18:34:53.953Z
Ryan O'Donnell
<p>ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average case?</p>

<p>Take average case to mean average running time with uniform distribution on the inputs.</p>

CC BY-SA 3.0
2012-12-04T11:00:36.617Z
you need a definition for "average case" to make your question a mathematically meaningful one.
Yixin Cao
CC BY-SA 3.0
2012-12-04T16:06:04.083Z
as I understand it, this is an open question which would have major implications in cryptography which requires such a mechanism for security... but there is research that is relevant eg SAT transition point research which shows there are "regions" where hard instances happen with high(er) probability. also much study of average case complexity... but note if you can prove that if any instance "chosen at random" from a set or distribution is definitely hard to solve, that would seem to prove P$\neq$NP.... so its a central question....
vzn
CC BY-SA 3.0
2012-12-04T21:30:08.820Z
vzn, I don't understand the relevance of your comment. I am not asking about an open problem here, it is obvious that there are no problems that are known to be hard on average. I am asking if there are any *candidates* that are *conjectured* to be hard in average case. Please read the question carefully before commenting.
Anonymous
CC BY-SA 3.0
2012-12-05T00:15:31.957Z
@Anonymous the point may be that any conjecture would have to be very carefully phrased to provide any insights or specific directions beyond the research mentioned. Perhaps the difference comes down to whether we are interested in a "conjecture" (which I think of as a nontrivial problem that may be solved as a stepping stone in a broader research programme) or rather a "consensus opinion" of the research community. For example, a conjecture such as "$P \neq NP$ and in addition, $3SAT$ is average-case hard" might not provide a tractable or illuminating target or inspire novel lines of work.
usul
CC BY-SA 3.0
2012-12-05T03:21:17.463Z
anonymous, you seem to be splitting hairs to me. cryptography is an excellent or foremost area to inquire in this area. also consider as another candidate the conjectures related to "breaking" random number generators as cited in Natural Proofs by razborov/rudich. feel free to downvote my comment if you disagree :p @usul, what would be the actual technical definition of "3SAT is average case hard"? defining what is meant by that in a technical way is apparently nontrivial and there is apparently more than one reasonable way to do it.
vzn
CC BY-SA 3.0
2012-12-05T03:31:23.753Z
@vzn Exactly! I definitely agree, my meaning is that it seems difficult for *any* such a conjecture to make a meaningful step forward or substantially change the directions of research that you mentioned.
usul
CC BY-SA 3.0
2012-12-05T03:33:52.347Z
OP, note that expected running time is not AFAIK the usual quantity we look at in average case hardness. see some survey on the average case complexity theory of Levin
Sasho Nikolov
CC BY-SA 3.0
2012-12-05T06:46:32.240Z
Sasho Nikolov, I am aware of Levin's theory. However there is also a simpler average case complexity used for analyzing the behavior of algorithms on a specific distribution going back to [Karp 1986] which is more common in algorithms. I am aware that the Tiling problem and a few other problems are complete for DistNP. However I don't know if they are conjectured to be exponentially hard on average using the simple meaning of average case due to Karp.
Anonymous
CC BY-SA 3.0
2012-12-06T04:22:05.020Z
I hereby conjecture that _every_ NP complete problem is exponentially hard for some average case distribution of inputs =)
vzn
CC BY-SA 3.0
2012-12-06T15:57:11.127Z
_dude_ its not a game. afaik it is in fact consistent with known theory to conjecture both that _every_ NP complete problem requires exponential time on average for some distribution over a region that includes "hard" instances, or that _no_ NP complete problem does either (eg that they all require only superpolynomial time)! or of course even that they all require only P time! hence its just a reformulation of P$\stackrel{?}{=}$NP. plz correct me if Im wrong! & you still havent really formally/strictly defined any of your critical terms of your question yet as the 1st comment pointed out....
vzn
CC BY-SA 3.0
2012-12-08T00:17:33.490Z
see also [aaronson on mathoverflow](http://mathoverflow.net/questions/3529/are-there-any-interesting-examples-of-random-np-complete-problems/31618#31618) answering gowers
vzn
<cc.complexity-theory><np><average-case-complexity>
Are there any known NP problems which are conjectured to be exponentially hard on average?
Anonymous
# Are there any known NP problems which are conjectured to be exponentially hard on average?

(Asked by: username_0 on 2012-12-04)

ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average case?

Take average case to mean average running time with uniform distribution on the inputs.

**Tags:** cc.complexity-theory, np, average-case-complexity
> **Comments:**
> **username_1**: you need a definition for "average case" to make your question a mathematically meaningful one.  
> **username_2**: as I understand it, this is an open question which would have major implications in cryptography which requires such a mechanism for security... but there is research that is relevant eg SAT transition point research which shows there are "regions" where hard instances happen with high(er) probability. also much study of average case complexity... but note if you can prove that if any instance "chosen at random" from a set or distribution is definitely hard to solve, that would seem to prove P$\neq$NP.... so its a central question....  
> **username_0**: vzn, I don't understand the relevance of your comment. I am not asking about an open problem here, it is obvious that there are no problems that are known to be hard on average. I am asking if there are any *candidates* that are *conjectured* to be hard in average case. Please read the question carefully before commenting.  
> **username_3**: @Anonymous the point may be that any conjecture would have to be very carefully phrased to provide any insights or specific directions beyond the research mentioned. Perhaps the difference comes down to whether we are interested in a "conjecture" (which I think of as a nontrivial problem that may be solved as a stepping stone in a broader research programme) or rather a "consensus opinion" of the research community. For example, a conjecture such as "$P \neq NP$ and in addition, $3SAT$ is average-case hard" might not provide a tractable or illuminating target or inspire novel lines of work.  
> **username_2**: anonymous, you seem to be splitting hairs to me. cryptography is an excellent or foremost area to inquire in this area. also consider as another candidate the conjectures related to "breaking" random number generators as cited in Natural Proofs by razborov/rudich. feel free to downvote my comment if you disagree :p @usul, what would be the actual technical definition of "3SAT is average case hard"? defining what is meant by that in a technical way is apparently nontrivial and there is apparently more than one reasonable way to do it.  
> **username_3**: @vzn Exactly! I definitely agree, my meaning is that it seems difficult for *any* such a conjecture to make a meaningful step forward or substantially change the directions of research that you mentioned.  
> **username_4**: OP, note that expected running time is not AFAIK the usual quantity we look at in average case hardness. see some survey on the average case complexity theory of Levin  
> **username_0**: Sasho Nikolov, I am aware of Levin's theory. However there is also a simpler average case complexity used for analyzing the behavior of algorithms on a specific distribution going back to [Karp 1986] which is more common in algorithms. I am aware that the Tiling problem and a few other problems are complete for DistNP. However I don't know if they are conjectured to be exponentially hard on average using the simple meaning of average case due to Karp.  
> **username_2**: I hereby conjecture that _every_ NP complete problem is exponentially hard for some average case distribution of inputs =)  
> **username_2**: _dude_ its not a game. afaik it is in fact consistent with known theory to conjecture both that _every_ NP complete problem requires exponential time on average for some distribution over a region that includes "hard" instances, or that _no_ NP complete problem does either (eg that they all require only superpolynomial time)! or of course even that they all require only P time! hence its just a reformulation of P$\stackrel{?}{=}$NP. plz correct me if Im wrong! & you still havent really formally/strictly defined any of your critical terms of your question yet as the 1st comment pointed out....  
> **username_2**: see also [aaronson on mathoverflow](http://mathoverflow.net/questions/3529/are-there-any-interesting-examples-of-random-np-complete-problems/31618#31618) answering gowers  

---

## 4 answers

### Answer by username_9 on 2012-12-05. Score: 13 | Accepted answer

It might be conjectured that the Learning Parity with Noise Problem (LPN) at constant error rate requires time $2^{n^{1-o(1)}}$. The fastest known algorithm (Blum-Kalai-Wasserman) uses time $2^{O(n/\log n)}$.

> **Comments:**
> **username_0**: Thank you. Could you please give references where I can read more about the LPN problem?  
> **username_10**: @Anonymous:  This paper states several conjectures on the hardness of LPN: M. Alekhnovich. “More on Average Case vs Approximation Complexity.” In Proc. of the 44th Symposium on Foundations of Computer Science, pp, 298—307, 2003.  
> **username_0**: Yury, thanks for the reference: http://www.math.ias.edu/~misha/papers/average.ps  

---

### Answer by username_5 on 2012-12-05. Score: 12

It's not quite the same as "every algorithm", but in SODA'04 Achlioptas Beame and Molloy suggested that every backtracking algorithm should require exponential time on random 3SAT instances with $n$ variables and $cn$ clauses, with $c$ chosen within a range of values near the satisfiability threshold.

> **Comments:**
> **username_0**: Thank you. Is there a reason they don't conjecture the stronger statement that random k-SAT restricted to clause ratio close to satisfiability threshold is exponentially hard?  
> **username_5**: My guess is that it's because they can prove results about backtracking algorithms that are not conditional on P≠NP.  

---

### Answer by username_6 on 2012-12-05. Score: 6

There are several psuedorandom number generators that we have no polynomial time algorithms for breaking. I guess you could consider them to be hard on average cases. Check out the generators at www.ecrypt.eu.org/stream/ There are others of course, you can research most of them online.

> **Comments:**
> **username_0**: Is there any particular polytime PRNG that is conjectured to be exponentially hard on average?  
> **username_6**: The Alternating Step Generator invented by Gunther is a beauty for several reasons. It takes two linear feedback shift registers(LFSR's) A & B and XOR's the outputs but the clocking of the two registers is controlled by a third LFSR(C) such that the outputs of A & B enter the XOR gate in an irregular manner. Becuase the bits of C only control the clocking of A & B and do not appear in the output stream, C can be considered a quasi hidden variable that breaks up the inherent linearity of A & B. This is a simplified explanation but you will want to see the circuit for yourself.  
> **username_0**: I am not familiar with "Alternating Step Generator invented by Gunther". Is it conjectured to be exponentially hard on average?  
> **username_6**: I don't know how to answer your comment as posed, but the ASG is considered to be unbreakable as long as the key lengths for the three shift registers are around 128 bits each. If this equates to being "exponentially hard on average" then I guess your answer is yes.  
> **username_0**: Hard to break in practice usually corresponds to polynomial hardness, not exponential hardness.  
> **username_7**: @Anonnymous: I don't know why you say that. The best algorithsm for RSA and Diffie-Hellman are both superpolynomial (although not exponential), and most good cryptosystems are believed to be asymptotically harder to break than these.  
> **username_6**: @Anonymous: Of course the "bare-bones" ASG can be made harder to break by using three ASG's as registers A B & C for another ASG, Gunther alludes to this in his original paper. It's like adding more rounds to a block cipher. How far one can amplify hardness by this method is an open question ( and interesting) :-)  
> **username_0**: Peter Shor, it should have been "superpolinomally hard". Are any of these cryptographic problems conjectured to be exponentially hard?  
> **username_6**: One could use communication complexity to analyze the complexity of breaking the ASG because the random clocking of the output registers causes them to have random ( or psuedorandom if you want to be picky) repeats , the same bit from one register is XOR'd with different bits from the other output register. So you can model each output register as being passed through a "sticky"channel. So you have one sticky channel performing a permutation on another sticky channel via the XOR function, that's pretty complex!  

---

### Answer by username_2 on 2012-12-05. Score: 0

my understanding is that while there are some candidates from the theory of unbreakability of cryptography and random number generators [eg some cited in Razborov/Rudich, Natural Proofs], most aspects of your question are acknowledged as basically key "still open" questions by experts in the field. from the introduction to the comprehensive survey, [*Average Case Complexity*](http://rads.stackoverflow.com/amzn/click/1933019492) by Bogdanov and Trevisan (2006) has some related points. Trevisan's [youtube lecture on findings and open questions of average case complexity](http://www.youtube.com/watch?v=Yo-naUur464) may also be helpful.

> Applying the theory to natural
> distributional problems remain an outstanding open question.  
> ...  
> A major open question is whether the existence of hard-on-average
> problems in NP can be based on the P$\neq$NP assumption or on related
> worst-case assumptions. We review negative results showing that certain
> proof techniques cannot prove such a result.  
> ...  
> In particular, a long-standing open question is whether it is possible
> to base the existence of one-way functions on the P$\neq$NP assumption,
> or related ones (such as NP-complete problems not allowing polynomial
> size circuits).  
> ...  
> The right techniques to apply such a theory to natural problems and
> distributions have not been discovered yet. From this point of view, the
> current state of the theory of average-case complexity in NP is similar
> to the state of the theory of inapproximability of NP optimization
> problems before the PCP Theorem.

> **Comments:**
> **username_0**: Not an answer to my question. I thought I have explained to you that I am not looking for general commentary on related issues, I am looking for *candidate problems conjectured to be hard*.  
> **username_2**: _whatever!_ imho "the theory does not have a substantial answer to your question at this point in time" along with some of the best/nearest avail refs/authorities on the subj is a legitimate answer to your question, which was posted not merely for _you_  
> **username_3**: @Anonymous, I am still a bit confused about your meaning of "conjectured". We all may have our personal conjectures, so it's not clear if you're looking for a personal opinion, a stance on an open question that is shared by many people in research, or something in between. It may help to give a more precise statement of what you're looking for. Also, I find answers such as vzn's to be instructive and informative even if they do not relate head-on to your exact question, so I don't see that such answers should be so strongly discouraged.  
> **username_2**: my understanding, it is _widely conjectured that such problems exist with some candidates_ via the one-way function theory but nailing down the details is apparently at least as hard or harder than resolving P$\neq$NP, partly due to subtleties in finding precise math definitions, and not coincidentally because its apparently tightly coupled to that same _conjecture_  
> **username_2**: moreover as in P.Shor's comment, there is possibly more conjecture about some problems being only _superpolynomial_ in their hardness... basically all conjectured-secure cryptosystems and random number generators (and they are all at this point _conjectured_ to be secure) are (at least implicitly but possibly not directly) conjectured to be of at least superpolynomial hardness....  
> **username_0**: If you have read my comment to which Peter Shor replied I am already aware of cryptographic problems that are conjectured to be superpolynomially hard. Please read the question carefully, I am not looking for superpolynomially hard problems, I am looking for exponentially hard ones.  
> **username_2**: obviously every problem that is at least superpolynomially hard is also a _candidate_ for an exponentially hard one so perhaps you already knew the answer to your own question before asking =)  
> **username_0**: usul, by "conjectured" I mean a "mathematical conjecture" as the term is used in mathematical literature: Goldbach's conjecture, unique games conjecture, P is not equal to NP conjecture, etc.  
> **username_0**: vzn, what you wrote is obviously false.  
> **username_8**: Please take further discussion to chat.  

---

