Average-Case Completeness



next up previous contents
Next: Polynomial-Time Reductions Up: Average-Case Computational Complexity Theory Previous: Average Polynomial Time

Average-Case Completeness

 

Given two distributional problems, we wish to know which one is computationally more difficult. The standard technique for such comparisons is to find a reduction from one problem to another. Levin [Lev86] provided a notion of reduction. Gurevich [Gur91a] advanced this theory in several ways that, at the same time, made Levin's ideas more accessible.





Jie Wang
Tue Feb 4 13:48:58 EST 1997