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 (Can't write to or create math temp directory): A, B, C, ...

denote various modules and their APIs.

Let Failed to parse (Can't write to or create math temp directory): 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 (Can't write to or create math temp directory): 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 (Can't write to or create math temp directory): x

or Failed to parse (Can't write to or create math temp directory): p

) to denote the version.

Let Failed to parse (Can't write to or create math temp directory): A_{x} \rightarrow B_{[u,v)}

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

Let Repository Failed to parse (Can't write to or create math temp directory): 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 (Can't write to or create math temp directory): R=(M,D) , if Failed to parse (Can't write to or create math temp directory): C \subseteq M , where following is satisfied:

1. each dependency is satisfied with some version from dependency range: Failed to parse (Can't write to or create math temp directory): \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 (Can't write to or create math temp directory): A_{x} \in C \wedge A_{y} \in C \Rightarrow x = y

Module Range Dependency Problem

Let there be a repository Failed to parse (Can't write to or create math temp directory): R = (M,D)

and a module Failed to parse (Can't write to or create math temp directory): A \in M

. Does there exist a configuration Failed to parse (Can't write to or create math temp directory): C

in the repository Failed to parse (Can't write to or create math temp directory): R

, such that the module Failed to parse (Can't write to or create math temp directory): 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 (Can't write to or create math temp directory): v_1, ..., v_m

as defined at in the original proof.

Let's create a repository of modules Failed to parse (Can't write to or create math temp directory): R . For each variable Failed to parse (Can't write to or create math temp directory): v_i

let's create two modules Failed to parse (Can't write to or create math temp directory): M^i_{1.0}
and Failed to parse (Can't write to or create math temp directory): M^i_{1.1}

, and put them into repository Failed to parse (Can't write to or create math temp directory): R .

For each formula Failed to parse (Can't write to or create math temp directory): (x_{i1} \vee x_{i2} \vee x_{i3})

let's create a module Failed to parse (Can't write to or create math temp directory): 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 (Can't write to or create math temp directory): v_a \vee \neg v_b \vee \neg v_c

we will get:

Failed to parse (Can't write to or create math temp directory): F^i_{1.1} \rightarrow M^a_{[1.1,1.1]}

Failed to parse (Can't write to or create math temp directory): F^i_{1.2} \rightarrow M^b_{[1.0,1.0]}

Failed to parse (Can't write to or create math temp directory): F^i_{1.3} \rightarrow M^c_{[1.0,1.0]}

All these modules and dependencies are added into repository Failed to parse (Can't write to or create math temp directory): R

Now we will create a module Failed to parse (Can't write to or create math temp directory): T_{1.0}

that depends on all formulas: 

Failed to parse (Can't write to or create math temp directory): T_{1.0} \rightarrow F^1_{[1.0,2.0)}

Failed to parse (Can't write to or create math temp directory): T_{1.0} \rightarrow F^2_{[1.0,2.0)}

...

Failed to parse (Can't write to or create math temp directory): T_{1.0} \rightarrow F^n_{[1.0,2.0)}

and add this module as well as its dependencies into repository Failed to parse (Can't write to or create math temp directory): R .

Claim: There Failed to parse (Can't write to or create math temp directory): \exists C

(a configuration) of repository Failed to parse (Can't write to or create math temp directory): R
and Failed to parse (Can't write to or create math temp directory): T_{1.0} \in C
Failed to parse (Can't write to or create math temp directory): \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.