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 an auxiliary graph technique to reduce the 3k-CLIQUE problem to the 3-CLIQUE problem, which is then solved in Ω(n2k) time.

Results: The research finds 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.

Implications: This result confirms a lower bound on the computational complexity of the 3k-CLIQUE problem, which has implications for the complexity of other graph problems and the boundary between P and NP.

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