Theoretical Computer Science
- cc.complexity-theory np average-case-complexity
- Updated Thu, 02 Jun 2022 05:46:51 GMT
-
Are there any known NP problems which are conjectured to be exponentially hard on average?
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.
Solution
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 (3)
- +0 – Thank you. Could you please give references where I can read more about the LPN problem? — Dec 05, 2012 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, 298307, 2003. — Dec 05, 2012 at 21:19
- +1 – Yury, thanks for the reference: math.ias.edu/~misha/papers/average.ps — Dec 06, 2012 at 05:04