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 Failed to parse (unknown error): A, B, C, ...

denote various modules and their APIs.

Let Failed to parse (unknown error): 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 Failed to parse (unknown error): 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 (Failed to parse (unknown error): x

or Failed to parse (unknown error): p

) to denote the version.

Let Failed to parse (unknown error): A_{x} \rightarrow B_{[u,v)}

denote the fact that version x of module A depends on version range Failed to parse (unknown error): [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 Failed to parse (unknown error): A_{x} \rightarrow B_{[u,v]}
denote closed interval dependency and allow its usage as well. 

Let Repository Failed to parse (unknown error): 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 Failed to parse (unknown error): R=(M,D) , if Failed to parse (unknown error): C \subseteq M , where following is satisfied:

1. each dependency is satisfied with some version from dependency range: Failed to parse (unknown error): \forall A_x \in C, \forall A_x \rightarrow B_{[u,v)} \in D \Rightarrow \exists w \in [u,v) \wedge B_{w} \in C

1. only one version is enabled: Failed to parse (unknown error): A_{x} \in C \wedge A_{y} \in C \Rightarrow x = y

Module Range Dependency Problem

Let there be a repository Failed to parse (unknown error): R = (M,D)

and a module Failed to parse (unknown error): A \in M

. Does there exist a configuration Failed to parse (unknown error): C

in the repository Failed to parse (unknown error): R

, such that the module Failed to parse (unknown error): A \in C , e.g. the module can be enabled?

Conversion of 3SAT to Module Range Dependencies Problem

Let there be 3SAT formula with variables Failed to parse (unknown error): v_1, ..., v_m

as defined at in the original proof.

Let's create a repository of modules Failed to parse (unknown error): R . For each variable Failed to parse (unknown error): v_i

let's create two modules Failed to parse (unknown error): M^i_{1.0}
and Failed to parse (unknown error): M^i_{1.1}

, and put them into repository Failed to parse (unknown error): R .

For each formula Failed to parse (unknown error): (x_{i1} \vee x_{i2} \vee x_{i3})

let's create a module Failed to parse (unknown error): 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 

Failed to parse (unknown error): v_a \vee \neg v_b \vee \neg v_c

we will get:

Failed to parse (unknown error): F^i_{1.1} \rightarrow M^a_{[1.1,1.1]}

Failed to parse (unknown error): F^i_{1.2} \rightarrow M^b_{[1.0,1.0]}

Failed to parse (unknown error): F^i_{1.3} \rightarrow M^c_{[1.0,1.0]}

All these modules and dependencies are added into repository Failed to parse (unknown error): R

Now we will create a module Failed to parse (unknown error): T_{1.0}

that depends on all formulas: 

Failed to parse (unknown error): T_{1.0} \rightarrow F^1_{[1.0,2.0)}

Failed to parse (unknown error): T_{1.0} \rightarrow F^2_{[1.0,2.0)}

...

Failed to parse (unknown error): T_{1.0} \rightarrow F^n_{[1.0,2.0)}

and add this module as well as its dependencies into repository Failed to parse (unknown error): R .

Claim: There Failed to parse (unknown error): \exists C

(a configuration) of repository Failed to parse (unknown error): R
and Failed to parse (unknown error): T_{1.0} \in C
Failed to parse (unknown error): \Longleftrightarrow
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.