Invisible wrote:
> Hmm, I wonder... If a problem is "NP-complete", does that actually mean 
> it's impossible to solve? Does it even mean it's necessarily difficult 
> to solve? I was under the impression that NP-complete merely means it 
> might take a long time to solve...

In practice, you should interpret a problem being NP-complete to mean 
that any known algorithm will have an exponential worst-case running 
time.  This does not necessarily mean that you can't efficiently solve 
the problem instances you encounter in practice, or that it's impossible 
to quickly solve for an approximate solution.  What sorts of efficiency 
gains are possible over the worse-case behavior of an exact algorithm 
will depend on the particulars of the problem and the domain to which 
you're applying it.

Post a reply to this message