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

Post a reply to this message

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? Have you even looked at the definition of "NP"?
It's a completely different category from the "non-solvable" category.

-- 
                                                          - Warp

Post a reply to this message

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

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

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

Post a reply to this message

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

Invisible <voi### [at] devnull> 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...

I would have thought this would really have driven the point home:

http://xkcd.com/287

 - Ricky

Post a reply to this message

triple_r <nomail@nomail> wrote:
> http://xkcd.com/287

  Except that the problem depicted there is not NP. It's O(1).

  (It would be NP as a generic problem with unlimited input. With a fixed
input and a fixed goal, it becomes O(1).)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   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.

It's a minor quibble, but I don't think this bit of reasoning holds. 
Integer factorization, for instance, has no known polynomial time 
algorithm but there are known sub-exponential algorithms.  Also (as I'm 
sure you know, but Andrew may not) polynomial time algorithms are 
considered part of the NP class, just as far as we know they're disjoint 
from the NP-complete class.

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

I found this picture handy in describing this relationship:

http://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg


One other point which I have messed up before and had Warp correct me 
on.  The NP and NP-complete complexity classes are for *decision 
problems* only.  That is algorithms which only return a boolean as their 
result.  If you want to refer to complexity classes for algorithms which 
  return more complicated results, the correct terms are FP (instead of 
P) and FNP (instead of NP).

Post a reply to this message

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

Warp wrote:
> triple_r <nomail@nomail> wrote:
>> http://xkcd.com/287
> 
>   Except that the problem depicted there is not NP. It's O(1).
> 
>   (It would be NP as a generic problem with unlimited input. With a fixed
> input and a fixed goal, it becomes O(1).)

Yes, but "General solutions get you a 50% tip", according to the comic
tooltip :D

Post a reply to this message

Kevin Wampler wrote:

> Integer factorization, for instance, has no known polynomial time 
> algorithm but there are known sub-exponential algorithms.

Really? I was under the impression that just recently - ah, wait. No, 
they found a polynomial-time primality test, but factorisation. Oh well.

> One other point which I have messed up before and had Warp correct me 
> on.  The NP and NP-complete complexity classes are for *decision 
> problems* only.

Yeah, I thought that was the case...

Post a reply to this message