Re: [boost] BGL: max clique?

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-03-04 15:07:57

On Sun, 4 Mar 2001, Phlip wrote:

ppluml> Proclaimed David Abrahams from the mountaintops:
ppluml> 
ppluml> > A previous poster has implied that this problem is proven NP-complete. That
ppluml> > means that if your algorithmicist has a polynomial solution, (s)he is about
ppluml> > to revolutionize computation. I guess in your shoes I would be preparing
ppluml> > myself to realize I had overlooked something ;-)
ppluml> 
ppluml> I thought "NP-complete" meant "solvable in polynomial
ppluml> time". Pretend I meant whatever response curve will not
ppluml> rock your world ;-)

Nope, "NP" stands for non-deterministic polynomial time. For this class of
problems, if you posit some answer to the problem, you can verify whether
or not the answer is correct in polynomial time. However, finding an
answer from scratch, or testing all possible answers, is not polynomial
time (or at least, no one has ever given a polynomial time algorithm for
an NP problem).

The "complete" part means that all problems in the NP-complete class can
be converted to eachother in polynomial time... if you solve one of the
problems in the class, you can solve any of the others.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------