Leonid A. Levin

Title: Leonid A. Levin

Research Question: Can random instances of a graph coloring problem be hard on average?

Methodology: The researchers used a random graph problem and introduced randomizing reductions to show the intractability of random instances of a graph coloring problem.

Results: The researchers proved that the graph problem is hard on average unless all NP problems under all samplable distributions are easy. This poses significant technical difficulties.

Implications: This work provides a strong hardness result related to "typical" or "average" instances of a problem, which is crucial for understanding the efficiency of algorithms and the P=NP question. It also shows that average case completeness of a random graph problem is unlikely without introducing randomizing reductions.

Link to Article: https://arxiv.org/abs/0112001v9 Authors: arXiv ID: 0112001v9