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
