Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
you need a definition for "average case" to make your question a mathematically meaningful one. – Yixin Cao Dec 4 '12 at 11:00
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 Dec 4 '12 at 21:30
@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 Dec 5 '12 at 3:31
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 Dec 5 '12 at 3:33
vzn, go play your games somewhere else. – Anonymous Dec 6 '12 at 5:01

4 Answers 4

up vote 11 down vote accepted

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)}$.

share|cite|improve this answer
Thank you. Could you please give references where I can read more about the LPN problem? – Anonymous Dec 5 '12 at 19:26
@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 Dec 5 '12 at 21:19
Yury, thanks for the reference: – Anonymous Dec 6 '12 at 5:04

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.

share|cite|improve this answer
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 Dec 6 '12 at 5:09
My guess is that it's because they can prove results about backtracking algorithms that are not conditional on P≠NP. – David Eppstein Dec 6 '12 at 6:28

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 There are others of course, you can research most of them online.

share|cite|improve this answer
Is there any particular polytime PRNG that is conjectured to be exponentially hard on average? – Anonymous Dec 5 '12 at 6:48
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 Dec 5 '12 at 7:39
I am not familiar with "Alternating Step Generator invented by Gunther". Is it conjectured to be exponentially hard on average? – Anonymous Dec 5 '12 at 9:05
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 Dec 5 '12 at 9:15
Hard to break in practice usually corresponds to polynomial hardness, not exponential hardness. – Anonymous Dec 5 '12 at 9:39

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 by Bogdanov and Trevisan (2006) has some related points. Trevisan's youtube lecture on findings and open questions of average case complexity 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.

share|cite|improve this answer
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 Dec 5 '12 at 19:13
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 Dec 5 '12 at 19:20
If you want to post your commentary for others to read please do so in some other place like a blog, not as answers to or comments on my question. – Anonymous Dec 5 '12 at 19:23
@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 Dec 5 '12 at 19:26
Please take further discussion to chat. – JɛffE Dec 5 '12 at 21:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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