Average Case Complexity of Graph Coloring Problems

Title: Average Case Complexity of Graph Coloring Problems

Abstract: This research study investigates the average case complexity of graph coloring problems. It presents a new approach to prove the hardness of random instances of a graph coloring problem, which is a well-known NP-complete problem. The study uses a concept analogous to NP-completeness, known as average case completeness, to show that the problem has no fast average case solution unless every NP problem under every samplable distribution has one. This result is significant because it provides a strong hardness result related to "typical" or "average" instances of the problem, which is of interest in the context of P = NP question.

Main Research Question: The main research question is whether there exists an average case solution to the graph coloring problem that can solve instances of the problem efficiently on "typical" or "average" inputs.

Methodology: The study uses a randomized reduction technique to prove the hardness of the graph coloring problem. The method involves creating a distribution over instances of the problem and then showing that the problem is hard on average under this distribution. The randomized reduction technique allows the study to handle problems with multiple colors and global restrictions, making it a more general and powerful approach than previous methods.

Results: The main result of the study is the average case completeness of the graph coloring problem. This means that the problem has no fast average case solution unless every NP problem under every samplable distribution has one. This result is significant because it provides a strong hardness result related to "typical" or "average" instances of the problem, which is of interest in the context of the P = NP question.

Implications: The results of this study have several implications. First, it provides a new approach to proving average case complexity for NP-complete problems. Second, it shows that the graph coloring problem is hard on average under certain conditions, which is of interest in the context of the P = NP question. Finally, the study's approach can be applied to other NP-complete problems, potentially leading to new average case complexity results for these problems.

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