Average-Case Computational Complexity Theory
Jie Wang

• Introduction
• Average Polynomial Time
• Average-Case Completeness
  • Polynomial-Time Reductions
  • Polynomial-Time Computable Distributions
  • Uniform Distributions
  • Distribution Controlling Lemma
  • Distributional NP-Completeness
  • Average Polynomial-Time Reductions
  • Distributional Search Problems
• Randomization
  • Flat Distributions and Incompleteness
  • Randomized Average Polynomial Time
  • Randomizing Reductions and Completeness
  • Polynomial-Time Sampling
  • Randomized Turing Reductions
• Hierarchies of Average-Case Complexity
  • Average-Time Hierarchies
  • Fast Convergence of Average Time
  • Averaging on Ranking of Distributions
• A Brief Survey of Other Results
• References
• About this document ...