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!

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?

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.