[Solved]: Computational complexity of the clique problem

Problem Detail: 

What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?

Asked By : loveToCode

Answered By : AJed

Wikipedia is usually a good starting reference to well-known problems as the clique. There is a list of the fastest known algorithms for CLIQUE including references.

Apparently, the fastest algorithm we know runs in time $O(1.1888^n)$, so that's the best upper bound on the complexity of CLIQUE we have. As for lower bounds, we don't have a super-polynomial one, or otherwise P=NP? would have been solved.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7112