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

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

Invisible wrote:
> 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.)

Yeah, that's basically correct.  It's a pretty well justified approach 
though since often NP-complete problems will take too long to solve 
practically in the average case as well as the worst case.

If you haven't done so before, it can be enlightening to write a program 
to solve some NP-complete problem by brute force, and then get a feel 
for how quickly its running time explodes on larger problems.  It's easy 
to rationally know what `exponential' means, but I've known many people 
to still be surprised when they see for themselves what that entails in 
real life.

What's the paper for out of curiosity?

Post a reply to this message

Kevin Wampler wrote:
> Invisible wrote:
>> 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.)
> 
> Yeah, that's basically correct.  It's a pretty well justified approach 
> though since often NP-complete problems will take too long to solve 
> practically in the average case as well as the worst case.
> 
> If you haven't done so before, it can be enlightening to write a program 
> to solve some NP-complete problem by brute force, and then get a feel 
> for how quickly its running time explodes on larger problems.  It's easy 
> to rationally know what `exponential' means, but I've known many people 
> to still be surprised when they see for themselves what that entails in 
> real life.
> 
> What's the paper for out of curiosity?

GraphViz paper on graph layout.

For example, finding a global arrangement of all graph nodes that 
minimises the number of edges that cross each other is meant to be 
NP-complete.

In this instance, the point is that finding *the* minimum number of 
crossings isn't hugely important, so long as the number can be kept 
reasonably small. But it's just the implication that this is impossibly 
difficult that bothered me. How long can it possibly take to try all 
possible permutations of 10 nodes?

Post a reply to this message

Invisible wrote:
> But it's just the implication that this is impossibly 
> difficult that bothered me. How long can it possibly take to try all 
> possible permutations of 10 nodes?

Really, try implementing a brute force algorithm and see for yourself 
how it scales.  Ten nodes may work, but what about twenty?  This is an 
important point since if you only have ten nodes you often don't really 
need a graph drawing program to visualize it.  It's when the graph 
becomes larger that it becomes really useful to automatically draw a 
nice picture of it.

If I remember correctly you wanted to draw trees though?  Edge crossings 
certainly wouldn't be a problem there.

Post a reply to this message

>> But it's just the implication that this is impossibly difficult that 
>> bothered me. How long can it possibly take to try all possible 
>> permutations of 10 nodes?
> 
> Really, try implementing a brute force algorithm and see for yourself 
> how it scales.  Ten nodes may work, but what about twenty?

Ah, I see. So you mean the problem is that *other people* might try to 
draw big graphs with it?

> If I remember correctly you wanted to draw trees though?  Edge crossings 
> certainly wouldn't be a problem there.

Trees that occasionally have nodes pointing back to their ancesters, 
yes. ;-)

Weirdly, GraphViz manages to come up with some *really* strange layouts 
- and refuses to obey my hints to lay the graph out the way I actually 
want it...

Post a reply to this message

Invisible wrote:
>>> But it's just the implication that this is impossibly difficult that 
>>> bothered me. How long can it possibly take to try all possible 
>>> permutations of 10 nodes?
>>
>> Really, try implementing a brute force algorithm and see for yourself 
>> how it scales.  Ten nodes may work, but what about twenty?
> 
> Ah, I see. So you mean the problem is that *other people* might try to 
> draw big graphs with it?

Heh, yeah I suppose that's the idea.  I think that "works with graphs of 
up to 12 nodes!" is maybe not the best feature for a piece of software 
to have.


>> If I remember correctly you wanted to draw trees though?  Edge 
>> crossings certainly wouldn't be a problem there.
> 
> Trees that occasionally have nodes pointing back to their ancesters, 
> yes. ;-)

Ahh, that makes sense.  If I remember you didn't want to order of the 
nodes to be able to change, in which case you really don't have as much 
choice


> Weirdly, GraphViz manages to come up with some *really* strange layouts 
> - and refuses to obey my hints to lay the graph out the way I actually 
> want it...

I haven't actually used the program, so I unfortunately can't be of much 
help here.  Since you have a small graph and pretty specific formatting 
requirements, what happened with the app you were writing yourself to do 
the layout?  You could also just draw it in inkscape of course if you 
want a really exact layout.

Post a reply to this message

>>>> But it's just the implication that this is impossibly difficult that 
>>>> bothered me. How long can it possibly take to try all possible 
>>>> permutations of 10 nodes?
>>>
>>> Really, try implementing a brute force algorithm and see for yourself 
>>> how it scales.  Ten nodes may work, but what about twenty?
>>
>> Ah, I see. So you mean the problem is that *other people* might try to 
>> draw big graphs with it?
> 
> Heh, yeah I suppose that's the idea.  I think that "works with graphs of 
> up to 12 nodes!" is maybe not the best feature for a piece of software 
> to have.

I wonder how big the graphs they use it for are? I mean, you can only 
fit a small number of nodes in a single drawing anyway...

>> Trees that occasionally have nodes pointing back to their ancesters, 
>> yes. ;-)
> 
> Ahh, that makes sense.  If I remember you didn't want to order of the 
> nodes to be able to change, in which case you really don't have as much 
> choice

Yeah, I basically already know the relative XY positions of the nodes, I 
just need to put in appropriate spacing and draw the edges nicely. (I 
haven't figured out how to control font selection with Cairo yet!)

>> Weirdly, GraphViz manages to come up with some *really* strange 
>> layouts - and refuses to obey my hints to lay the graph out the way I 
>> actually want it...
> 
> I haven't actually used the program, so I unfortunately can't be of much 
> help here.  Since you have a small graph and pretty specific formatting 
> requirements, what happened with the app you were writing yourself to do 
> the layout?

I think I'm going to reimplement it in light of what I've learned from 
GraphViz. (E.g., it uses invisible nodes that don't show up on the 
drawing, but *do* help it to route edges so they don't collide. I can 
copy that easily enough.)

Post a reply to this message

Invisible wrote:
> I wonder how big the graphs they use it for are? I mean, you can only 
> fit a small number of nodes in a single drawing anyway...

I'd guess that a few tens to a few hundred nodes is not too uncommon.  I 
have seen some graph drawings with millions of nodes, but generally 
these aren't DAGs and are thus drawn with a different technique.


> I think I'm going to reimplement it in light of what I've learned from 
> GraphViz. (E.g., it uses invisible nodes that don't show up on the 
> drawing, but *do* help it to route edges so they don't collide. I can 
> copy that easily enough.)

I'll be interested to see how it looks.  I assume you'll also be 
dropping the bounding box for collision avoidance? :)

Post a reply to this message

>> I wonder how big the graphs they use it for are? I mean, you can only 
>> fit a small number of nodes in a single drawing anyway...
> 
> I'd guess that a few tens to a few hundred nodes is not too uncommon.

...Jesus Christ! o_O

OK, sure, you definitely don't want to use an NP-complete algorithm. :-}

>> I think I'm going to reimplement it in light of what I've learned from 
>> GraphViz. (E.g., it uses invisible nodes that don't show up on the 
>> drawing, but *do* help it to route edges so they don't collide. I can 
>> copy that easily enough.)
> 
> I'll be interested to see how it looks.  I assume you'll also be 
> dropping the bounding box for collision avoidance? :)

Yeah, I'm not overly worried about a few lines crossing. I may or may 
not need to do something about avoiding one path being partially on top 
of another for any great length though...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> I may or may 
> not need to do something about avoiding one path being partially on top 
> of another for any great length though...

Assuming you're using invisible nodes to route long edges I don't think 
it's possible to have coincident edges, so unless I'm mistaken this 
shouldn't be an issue.

Post a reply to this message

>> I may or may not need to do something about avoiding one path being 
>> partially on top of another for any great length though...
> 
> Assuming you're using invisible nodes to route long edges I don't think 
> it's possible to have coincident edges, so unless I'm mistaken this 
> shouldn't be an issue.

Hmm. If you ensure that all routing is from one row to the adjacent row, 
then no, it shouldn't be possible. Good point! (Should also be 
impossible for an edge to cross a node.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message