Re: [boost] BGL: max clique?

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-03-04 15:21:12

----- Original Message -----
From: "Phlip" <pplumlee_at_[hidden]>

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

The "N" stands for "Non-" and the "P" stands for "Polynomial". AFAIK nobody
has been able to prove that NP-complete problems can't be solved in
polynomial time, but it is proven that if any of them can be so solved, all
of them can be... and so far nobody has managed to solve any of them in
polynomial time.

-Dave