Average-Case NP-Complete Problems

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

• 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