Average-Case Intractable NP Problems
Jie Wang

• Introduction
• Preliminaries
  • Average Polynomial Time
  • Polynomial-Time Reductions
  • Polynomial-Time Computable Distributions
  • Uniform Distributions
  • Distribution Controlling Lemma
• Average-Case NP-Complete Problems
  • Distributional Halting Problem (Version 1)
  • Distributional Tiling Problem
  • Distributional Post Correspondence and Related Problems
  • Distributional String-Rewriting Problems
  • Distributional Word Problem for Groups
  • Distributional Halting Problem (Version 2)
  • Distributional Graph Edge Coloring Problem
  • Distributional Matrix Correspondence Problem
  • Distributional Matrix Transformation Problem
  • Distributional Matrix Representability Problem
• Completeness Proofs (Part I)
  • Distributional Halting (Version 1)
  • Distributional Tiling
• Completeness Proofs (Part II)
  • Dynamic Coding Scheme
  • Distributional Post Correspondence
  • Distributional String-Rewriting
  • Distributional Word Problem for Groups
• Completeness Proofs (Part III)
  • Randomized Reductions
  • Distributional Halting (Version 2)
  • Distributional Graph Edge Coloring
  • Distributional Matrix Correspondence
  • Distributional Matrix Transformation
• Final Remarks and Open Problems
• References
• About this document ...