Skip to main content
Post Made Community Wiki
Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

How about Leonid Levin (1986), Average-Case Complete Problems, SIAM Journal of Computing 15: 285-286? Quite important in complexity theory, and only two pages long, although very, very dense.