RangeDependenciesNP
From APIDesign
From the things described so far it seems that RangeDependencies may not be as bad, but still, there are severe NP-Complete problems associated with them. Following sections demonstrate the problems.
Module Repository with Ranges
Let A,B,C,... denote various modules and their APIs.
Let A_{1.0},A_{1.1},A_{1.7},A_{1.11},A_{2.1},A_{2.9},A_{3.0} denote versions of module A. It is not really important what format the versions use, the only condition is that there is a linear order among the versions. As such the rest of the terminology is using single variable (x or p) to denote the version.
Let denote the fact that version x of module A depends on version range [u,v) of module B. E.g. any version of module B between u and less than v can be used to satisfy A's need. Let denote closed interval dependency and allow its usage as well.
Let Repository R = (M,D) be any set of modules with their versions and their dependencies on other modules.
Let C be a Configuration in a repository R = (M,D), if , where following is satisfied:
- each dependency is satisfied with some version from dependency range:
- only one version is enabled:
Module Range Dependency Problem
Let there be a repository R = (M,D) and a module . Does there exist a configuration C in the repository R, such that the module , e.g. the module can be enabled?
Conversion of 3SAT to Module Range Dependencies Problem
Let there be 3SAT formula with variables v_{1},...,v_{m} as defined at in the original proof.
Let's create a repository of modules R. For each variable v_{i} let's create two modules and , and put them into repository R.
For each formula let's create a module F^{i} that will have three versions. Each of them will depend on one variable's module. In case the variable is used with negation, it will depend on version 1.0, otherwise on version 1.1. So for formula
we will get:
All these modules and dependencies are added into repository R
Now we will create a module T_{1.0} that depends on all formulas:
- ...
and add this module as well as its dependencies into repository R.
Claim: There (a configuration) of repository R and there is a solution to the 3SAT formula.
The proof is step by step similar to the one given in LibraryReExportIsNPComplete, so it is not necessary to repeat it here.