Question

the decision-clique problem is the problem of determining whether a graph G contains
a clique of at least a given size k. This problem is NP-complete.
Professor Bartlett has designed an algorithm that can take any graph G with n vertices and
determine in O(nk ) time whether or not G contains a clique of size k. Has Professor Bartlett
showed that P = NP? Explain your answer.

Answer 1

The Clique problem is known to be a typical NP-complete problem, and hence it is believed to be impossible to solve it in polynomial-time.

Using a brute force algorithm. This algorithm examines each subgraph with k vertices and checks to see whether it forms a clique. It takes time O(n^kk²), as expressed using big O notation. This is because there are O(n^k) subgraphs to check, each of which has O(k²) edges whose presence in G needs to be checked. Thus, the problem may be solved in polynomial time whenever k is a fixed constant. However, when k does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential.

Here, since we take the assumption that the professor has already found an algorithm to find clique in O(nk) time, Clique problem can be solved in polynomial time, hence P = NP for Clique problem.

Since P = NP for Clique problem, hence showed P = NP .