Kevin Wampler wrote:

> 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.

The paper I'm looking at has several places where the program has to 
guess a solution that is "good enough" because finding the perfect 
solution is "NP-complete". Makes it sound like solving such a problem is 
somehow "impossible" - but as you say, all it really means is that it's 
slow. (Or at least, *potentially* slow.)

Post a reply to this message