Computer Science – Computational Complexity
Scientific paper
2006-06-08
Computer Science
Computational Complexity
Scientific paper
We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect to all samplable distributions. Applying the theory to natural distributional problems remain an outstanding open question. We review some natural distributional problems whose average-case complexity is of particular interest and that do not yet fit into this theory. A major open question 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. While the relation between worst-case and average-case complexity for general NP problems remains open, there has been progress in understanding the relation between different ``degrees'' of average-case complexity. We discuss some of these ``hardness amplification'' results.
Bogdanov Andrej
Trevisan Luca
No associations
LandOfFree
Average-Case Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Average-Case Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Average-Case Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-506869