What is (Re:) NP-Completeness?

[Peter Kriens]

In theory practice and theory are the same, in practice they tend to differ ...

The OSGi has its fair share of complaints but resolving time is definitely not one of them. OSGi is used by some very, very large applications with thousands of bundles ... Am I missing something here?

Don't get me wrong, the theoretical work is crucial and we're not doing enough of it in our industry. However, the fact that you prove that a problem is translatable into an NP complete problem does not mean it cannot perform in reasonable time since the real world problem usually has lots of pruning capabilities, heuristics, and require "a" solution not an optimal solution.

And I do not think the problem is going once through every town since this set is based on who you visit. The resolving problem is more that you should not pass through any town that is unacceptable by any of the other towns you visit/visited.

Kind regards,

	Peter Kriens

P.S. Nav systems optimize for highways, toll roads, so it has similar problems.


On 23 dec. 2011, at 10:54, Jaroslav Tulach wrote:
>> ## 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.
>