RangeDependenciesNP

From APIDesign

Revision as of 20:25, 7 May 2012 by JaroslavTulach (Talk | contribs)

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

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 $A_{x} \rightarrow B_{[u,v)}$ 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 $A_{x} \rightarrow B_{[u,v]}$ 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 $C \subseteq M$ , where following is satisfied:

each dependency is satisfied with some version from dependency range: $\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$
only one version is enabled: $A_{x} \in C \wedge A_{y} \in C \Rightarrow x = y$

Module Range Dependency Problem

Let there be a repository $R = (M, D)$ and a module $A \in M$ . Does there exist a configuration $C$ in the repository $R$ , such that the module $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 $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 $M^i_{1.0}$ and $M^i_{1.1}$ , and put them into repository $R$ .

For each formula $(x_{i1} \vee x_{i2} \vee x_{i3})$ 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