Home » forums » LtU Forum

Usage of Range Dependencies may not Lead to NP-Complete Problems

Two years ago I got your comments about NP-complete Library Versioning Problem and Proper Library Versioning no longer NP-Complete and I even demonstrated on OSGi's range dependencies that situations of this kind are not unlikely to happen in real projects.

Since then I thought that the root of all evil is the usage of range dependencies. Now I think I was wrong. With the help of complete repositories one can elimiante the NP-Complete problems by encoding all transitive dependencies during compilation.

I've summarized my recent findings into a proof. I'll be glad if LtU audience helps me review it. Thanks and happy new year!

By Jaroslav Tulach at 2012-01-09 10:44 | LtU Forum | previous forum topic | next forum topic | other blogs | 4647 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Can you explain your definition of completeness?

If A depends on B[u ... v], why does the transitivity requirement only involve the dependencies of B[u]? Aren't the dependencies of the versions of a module arbitrary and unrelated?

By Matt M at Wed, 2012-01-11 14:22 | login or register to post comments

The lower bound - e.g. B[u]

The lower bound - e.g. B[u] - is the version used during compilation of module A. At that moment A may not have any need to direct require on C and in such case (and in order to make the repository complete) the module A implicitly inherits the dependency used by B[u].

On the other hand, A may have some specific requirements on C and in such case it can narrow the interval of B[u]'s dependency on C to match A's needs.

By Jaroslav Tulach at Thu, 2012-02-02 09:12 | login or register to post comments