The Computational Complexity of 3k-CLIQUE
Title: The Computational Complexity of 3k-CLIQUE
Research Question: What is the minimum time complexity required for a deterministic and exact algorithm to solve 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 3k-CLIQUE problem on the original graph is then reduced to determining if there is a nonzero entry in the product of the adjacency matrices of the auxiliary graph.
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 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 implications for the field of computational complexity, as it provides a lower bound on the time complexity of solving the 3k-CLIQUE problem. It also contributes to the ongoing discussion about the relationship between P and NP, as the lower bound implies that P/NP ≠ P.
Link to Article: https://arxiv.org/abs/0310060v11 Authors: arXiv ID: 0310060v11