What is (Re:) NP-Completeness?
jaroslav.tulach at oracle.com
Fri Dec 23 01:54:49 PST 2011
>## 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
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
> 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
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.
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
More information about the jigsaw-dev