The Computational Complexity of 3k-CLIQUE

Title: The Computational Complexity of 3k-CLIQUE

Research Question: How fast can a deterministic and exact algorithm solve the 3k-CLIQUE problem on a classical computer?

Methodology: The study uses a graph theory approach to solve the 3k-CLIQUE problem. It proposes a method where an auxiliary graph G′ is created, which has a 3-clique if and only if the 3k-CLIQUE problem is true for the original graph G. The Hadamard product of the adjacency matrix of G′ is then used to determine if there is a 3-clique in G′.

Results: The main result is that the fastest deterministic and exact algorithm that solves the 3k-CLIQUE problem must run in Ω( n2k) time in the worst-case scenario on a classical computer, where n is the number of vertices in the graph. This implies that P/negationslash ≠ NP, which is a significant contribution to the complexity theory.

Implications: This research has practical implications for the field of computer science, particularly in the areas of graph theory and computational complexity. It sets a lower bound on the time complexity for solving the 3k-CLIQUE problem, which has applications in various areas such as combinatorics, artificial intelligence, and network analysis. The results also contribute to our understanding of the relationship between NP and P/negationslash classes.

Link to Article: https://arxiv.org/abs/0310060v12 Authors: arXiv ID: 0310060v12