14

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.

Anonymous
  • 4,041
  • 19
  • 43
  • 6
    you need a definition for "average case" to make your question a mathematically meaningful one. – Yixin Cao Dec 04 '12 at 11:00
  • 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 Dec 04 '12 at 16:06
  • 2
    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 04 '12 at 21:30
  • @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 Dec 05 '12 at 00:15
  • 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 Dec 05 '12 at 03:21
  • 1
    @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 05 '12 at 03:31
  • 3
    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 05 '12 at 03:33
  • 1
    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 Dec 05 '12 at 06:46
  • I hereby conjecture that every NP complete problem is exponentially hard for some average case distribution of inputs =) – vzn Dec 06 '12 at 04:22
  • 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 Dec 06 '12 at 15:57
  • see also aaronson on mathoverflow answering gowers – vzn Dec 08 '12 at 00:17

4 Answers4

13

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

Ryan O'Donnell
  • 1,811
  • 17
  • 21
  • Thank you. Could you please give references where I can read more about the LPN problem? – Anonymous Dec 05 '12 at 19:26
  • 2
    @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 05 '12 at 21:19
  • 1
    Yury, thanks for the reference: http://www.math.ias.edu/~misha/papers/average.ps – Anonymous Dec 06 '12 at 05:04
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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • 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 06 '12 at 05:09
  • 4
    My guess is that it's because they can prove results about backtracking algorithms that are not conditional on P≠NP. – David Eppstein Dec 06 '12 at 06:28
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.

William Hird
  • 231
  • 2
  • 4
  • Is there any particular polytime PRNG that is conjectured to be exponentially hard on average? – Anonymous Dec 05 '12 at 06: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 05 '12 at 07:39
  • I am not familiar with "Alternating Step Generator invented by Gunther". Is it conjectured to be exponentially hard on average? – Anonymous Dec 05 '12 at 09:05
  • 1
    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 05 '12 at 09:15
  • Hard to break in practice usually corresponds to polynomial hardness, not exponential hardness. – Anonymous Dec 05 '12 at 09:39
  • @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 Dec 05 '12 at 12:02
  • 1
    @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 Dec 05 '12 at 14:15
  • Peter Shor, it should have been "superpolinomally hard". Are any of these cryptographic problems conjectured to be exponentially hard? – Anonymous Dec 05 '12 at 19:15
  • 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 Dec 06 '15 at 20:16
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 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.

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 2
    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 05 '12 at 19:13
  • 1
    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 05 '12 at 19:20
  • 1
    @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 05 '12 at 19:26
  • 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 Dec 05 '12 at 19:26
  • 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 Dec 05 '12 at 19:38
  • 2
    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 Dec 05 '12 at 19:46
  • 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 Dec 05 '12 at 19:48
  • 1
    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 Dec 05 '12 at 19:49
  • 1
    vzn, what you wrote is obviously false. – Anonymous Dec 05 '12 at 19:50
  • 2
    Please take further discussion to chat. – Jeffε Dec 05 '12 at 21:30