The Computational Complexity of 3k-CLIQUE: Difference between revisions
Created page with "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 origina..." |
No edit summary |
||
| Line 1: | Line 1: | ||
Title: The Computational Complexity of 3k-CLIQUE | Title: The Computational Complexity of 3k-CLIQUE | ||
Research Question: What is the minimum time complexity for | 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 | 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 | 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: 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/ | Link to Article: https://arxiv.org/abs/0310060v11 | ||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0310060v11 | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
[[Category: | [[Category:3K]] | ||
[[Category:Clique]] | [[Category:Clique]] | ||
[[Category:Graph]] | [[Category:Graph]] | ||
[[Category:Problem]] | |||
[[Category:Complexity]] | [[Category:Complexity]] | ||
Revision as of 14:46, 24 December 2023
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