Can Random Graphs Be Hard?

Title: Can Random Graphs Be Hard?

Research Question: Can random instances of a graph coloring problem be hard on average, even though other similar problems are easy for random inputs?

Methodology: The researchers used a technique called "average case completeness." This involves showing that a problem has no fast average case solution unless every NP problem under every samplable distribution has one. This is a stronger hardness result than traditional NP-completeness, as it is sensitive to the choice of a particular NP-complete problem and the input distribution.

Results: The researchers introduced a new problem called the colored 3-graph coloring problem. They showed that this problem is hard on average under a specific distribution of colors and a global parameter called "k." They also provided examples of other graph problems that can be expressed using this formalism.

Implications: This research has implications for the field of computer science and complexity theory. It suggests that random graph problems can be hard on average, even though other similar problems might be easy for random inputs. This could have implications for the design of algorithms and the solution of complex problems in various fields.

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