The Computational Complexity of 3k-CLIQUE

Title: The Computational Complexity of 3k-CLIQUE

Research Question: What is the minimum time complexity for solving the 3k-CLIQUE problem on a classical computer?

Methodology: The study uses a graph theoretical approach to solve the 3k-CLIQUE problem. It proposes a method to convert the original graph into an auxiliary graph with a specific structure. The 3-CLIQUE problem on the auxiliary graph is then solved, which is equivalent to the 3k-CLIQUE problem on the original graph. The time complexity of this method is analyzed and a lower bound of Ω(n2k) is derived.

Results: The research shows 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. This lower bound is confirmed by the fact that the fastest known deterministic and exact algorithm that solves 3k-CLIQUE was published in 1985 and has a running time of Θ(nωk), where ω ≥ 2.

Implications: This research has important implications for the field of computational complexity. It provides a lower bound on the time complexity of solving the 3k-CLIQUE problem, which is a fundamental problem in graph theory. The results suggest that there may be no faster deterministic and exact algorithms for this problem on a classical computer. This could have implications for the classification of the P/NP-complete problem space.

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