The Computational Complexity of 3k-CLIQUE

From Simple Sci Wiki
Revision as of 14:46, 24 December 2023 by SatoshiNakamoto (talk | contribs)
Jump to navigation Jump to search

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