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 graph theory and matrix theory to propose a method for solving the 3k-CLIQUE problem. It creates an auxiliary graph G' with O(nk) vertices and O(n2k) edges, equivalent to the 3-CLIQUE problem on the original graph G. The study then proposes a way to determine if there exists a 3-clique in G' by checking if a certain equation holds true for each pair of vertices.

Results: The main result is that any deterministic and exact algorithm that does not use an oracle must take Ω(n2k) time in the worst-case scenario to solve the 3k-CLIQUE problem. This is because there are adjacency matrices with Θ(n2k) indices such that the equation holds true, but only a constant number of indices have the equation hold false.

Implications: This lower bound on the time complexity implies that P/∧≠NP, meaning that there are problems that are inherently harder to solve approximately than exactly. This is a significant result in the field of computational complexity.

In conclusion, the study shows that determining if a 3k-clique exists in a graph requires at least Ω(n2k) time in the worst-case scenario for a deterministic and exact algorithm. This lower bound holds even for the fastest known algorithms, implying that some problems are fundamentally harder to solve than others.

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