Invisible <voi### [at] devnull> wrote:
> >> Hmm, I wonder... If a problem is "NP-complete", does that actually mean 
> >> it's impossible to solve?
> > 
> >   What makes you think that?

> Statements like "we use the following heuristic since actually solving 
> [problem X] is NP-complete". This kind of implies that NP-complete = 
> impossible to solve.

  It doesn't imply "impossible to solve". It implies "impossible to solve
in a rational amount of time". People do not have millenia of time to
wait for the program to given a solution.

> > Have you even looked at the definition of "NP"?

> Yes. Several times. Needless to say, I didn't really understand it very 
> well.

  Basically the NP complexity class is composed of those problems for
which the solution cannot, as far as we currently know, be solved in
polynomial time using a deterministic computer (which means that solving
the problem requires at least exponential time), but if a solution is
given, the solution can be verified in polynomial time.

  A problem is "NP-complete" if it can be transformed in polynomial time
into any other NP problem. What this means in practice is that if you ever
find a polynomial-time solution to some specific NP-complete problem, that
exact same solution can be used to solve *all* NP problems in polynomial
time.

  (Note that a solution to an NP-complete problem might not be usable as
a solution to the so-called NP-hard problems, so it makes a difference
whether a problem is NP or NP-hard.)

-- 
                                                          - Warp

Post a reply to this message