What is (Re:) NP-Completeness?

[Jaroslav Tulach]

>## 23. 12. 2011 09:35:01 ##<
> First, Richard S. Hall's resolver in Felix has shown that even large
> systems resolve in a very short time and using very few electrons on the
> way. 

I am sure Jesse can modify his simple sample to generate few OSGi bundles and 
make Felix spend all its time resolving dependencies until its computer turns 
into dust.

> And he resolves with a completely generic require/capabilities model
> including the so called uses constraints necessary to support side-by-side
> versioning. If google maps can find a route between Montpellier and
> Stockholm in less than a second then I fail to see why we could not find a
> route in the much smaller space of software dependencies.

I don't want to occupy this mailing list with computer science topic, however 
I have to point out this faux pas for the benefit of everyone who will try to 
understand why having systems with inherent NP-complete problems is no good.

However complicated the task of finding a route between two towns may seem, it 
is a simple graph algorithm which can be solved in O((n+m)*log(n)) steps. Thus 
trying to deduce from the performance of google maps anything with respect to 
module systems with range dependencies is meaningless.

When talking about maps I can give you another task which would be NP-
complete: Find a route from Montpelier to Stockholm that visits every town 
larger than 10000 citizens in France, Germany, Denmark and Sweden exactly 
once. 

If you try this, you'll find out it is much more complicated tasks then 
finding a shortest path between two towns. I am sure even google maps would 
not handle problem of this size in 1s.
-jt

PS: If anyone knew how to effectively find a route through passing once every 
town, then we would also have effective algorithm for resolving range 
dependencies.