14
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 6
    $\begingroup$ you need a definition for "average case" to make your question a mathematically meaningful one. $\endgroup$
    – Yixin Cao
    Commented Dec 4, 2012 at 11:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – Anonymous
    Commented Dec 4, 2012 at 21:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – usul
    Commented Dec 5, 2012 at 3:31
  • 3
    $\begingroup$ 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 $\endgroup$
    – Sasho Nikolov
    Commented Dec 5, 2012 at 3:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Anonymous
    Commented Dec 5, 2012 at 6:46

4 Answers 4

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you. Could you please give references where I can read more about the LPN problem? $\endgroup$
    – Anonymous
    Commented Dec 5, 2012 at 19:26
  • 2
    $\begingroup$ @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. $\endgroup$
    – Yury
    Commented Dec 5, 2012 at 21:19
  • 1
    $\begingroup$ Yury, thanks for the reference: math.ias.edu/~misha/papers/average.ps $\endgroup$
    – Anonymous
    Commented Dec 6, 2012 at 5:04
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Anonymous
    Commented Dec 6, 2012 at 5:09
  • 4
    $\begingroup$ My guess is that it's because they can prove results about backtracking algorithms that are not conditional on P≠NP. $\endgroup$
    – David Eppstein
    Commented Dec 6, 2012 at 6:28
6
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Is there any particular polytime PRNG that is conjectured to be exponentially hard on average? $\endgroup$
    – Anonymous
    Commented Dec 5, 2012 at 6:48
  • $\begingroup$ 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. $\endgroup$
    – William Hird
    Commented Dec 5, 2012 at 7:39
  • $\begingroup$ I am not familiar with "Alternating Step Generator invented by Gunther". Is it conjectured to be exponentially hard on average? $\endgroup$
    – Anonymous
    Commented Dec 5, 2012 at 9:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – William Hird
    Commented Dec 5, 2012 at 9:15
  • 1
    $\begingroup$ @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) :-) $\endgroup$
    – William Hird
    Commented Dec 5, 2012 at 14:15
0
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Anonymous
    Commented Dec 5, 2012 at 19:13
  • 1
    $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Dec 5, 2012 at 19:20
  • 1
    $\begingroup$ @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. $\endgroup$
    – usul
    Commented Dec 5, 2012 at 19:26
  • 2
    $\begingroup$ 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. $\endgroup$
    – Anonymous
    Commented Dec 5, 2012 at 19:46
  • 2
    $\begingroup$ Please take further discussion to chat. $\endgroup$
    – Jeffε
    Commented Dec 5, 2012 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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