Average-Case NP-Complete Problems



next up previous contents
Next: Distributional Halting Problem Up: Average-Case Intractable NP Problems Previous: Distribution Controlling Lemma

Average-Case NP-Complete Problems

 

Given below is a list of best-known average-case NP-complete problems that have been published so far.





Jie Wang
Mon Feb 3 15:13:50 EST 1997