# LibraryReExportIsNPComplete

### From APIDesign

(→Module Dependencies Problem) |
(→Module Dependencies Problem) |
||

Line 21: | Line 21: | ||

Let <math>A_{x.y} \rightarrow B_{u.v}</math> denote the fact that version ''x.y'' of API A depends on version ''u.v'' of API ''B''. | Let <math>A_{x.y} \rightarrow B_{u.v}</math> denote the fact that version ''x.y'' of API A depends on version ''u.v'' of API ''B''. | ||

- | Let <math>A_{x.y} \ | + | Let <math>A_{x.y} \leadsto B_{u.v}</math> denote the fact that version ''x.y'' of API A depends on version ''u.v'' of API ''B'' and that ''B'' re-exports its elements. |

- | Let | + | Let ''Repository'' <math>R=(M,D)</math> be any set of modules with their various versions and their dependencies on other modules with or without re-export. |

- | Let '' | + | Let C be a ''Configuration'' in a repository <math>R=(M,D)</math>, if |

+ | <math>C \subseteq M</math>, where following conditions are satisfied: | ||

+ | :<math>A_{x.y} \in C \vee A_{u.v} \in C \Rightarrow x = u \vee y = v</math> | ||

+ | : | ||

+ | |||

+ | Let <math>Dep_R(A_{x.y})</math> be set of all modules in repository <math>R</math> that M depends on directly. E.g. | ||

+ | <math>Dep_R(A_{x.y}) = { B_{u.v} : A_{x.y} \rightarrow B_{u.v} \wedge | ||

+ | A_{x.y} \rightarrow B_{u.v} }</math>. | ||

Let say that a repository is '''Executable''' if there exists as subset of the set of modules from the repository, where each module is present in only one version and dependencies of a modules are satisfied in the subset and no module ''sees'' any class exported by a module twice. | Let say that a repository is '''Executable''' if there exists as subset of the set of modules from the repository, where each module is present in only one version and dependencies of a modules are satisfied in the subset and no module ''sees'' any class exported by a module twice. |

## Revision as of 09:40, 25 May 2008

This page describes a way to convert any wikipedia::3SAT problem to a solution of finding the right configuration from conflicting libraries in a system that can re-export APIs. Thus proving that the later problem is wikipedia::NP-complete.

## wikipedia::3SAT

The problem of satisfying a logic formula remains **NP**-complete even if all expressions are written in *wikipedia::conjunctive normal form* with 3 variables per clause (3-CNF), yielding the **3SAT** problem. This means the expression has the form:

- ...

where each *x*_{ab} is a variable *v*_{i} or a negation of a variable . Each variable *v*_{i} can appear multiple times in the expression.

## Module Dependencies Problem

Let *A*,*B*,*C*,... denote an API.

Let *A*_{1},*A*_{1.1},*A*_{1.7},*A*_{1.11} denote compatible versions of API *A*.

Let *A*_{1},*A*_{2.0},*A*_{3.1} denote incompatible versions of API *A*.

Let denote the fact that version *x.y* of API A depends on version *u.v* of API *B*.

Let **Failed to parse (Can't write to or create math temp directory): A_{x.y} \leadsto B_{u.v}**

denote the fact that versionx.yof API A depends on versionu.vof APIBand thatBre-exports its elements.

Let *Repository* *R* = (*M*,*D*) be any set of modules with their various versions and their dependencies on other modules with or without re-export.

Let C be a *Configuration* in a repository *R* = (*M*,*D*), if
, where following conditions are satisfied:

Let *D**e**p*_{R}(*A*_{x.y}) be set of all modules in repository *R* that M depends on directly. E.g.
.

Let say that a repository is **Executable** if there exists as subset of the set of modules from the repository, where each module is present in only one version and dependencies of a modules are satisfied in the subset and no module *sees* any class exported by a module twice.

## Converstion of wikipedia::3SAT to Module Dependencies Problem

Let
(*x*_{a} or ¬*x*_{b} or ¬*x*_{c}) and (*x*_{a} or *x*_{b} or *x*_{d})
be a formula. For each variable *x*_{a} let's create two modules with incompatible version *A*_{1} and *A*_{2} and put them into the repository of modules.

For each formula let's create a module *F* that will have three compatible versions. Each of them will depend on one variable. In case the variable is used with negation, it will depend on version *2*, otherwise on version *1*. So for the formula
(*x*_{a} or ¬*x*_{b} or ¬*x*_{c})
we will get:
*F*_{1.1}[^*A*_{1}] and
*F*_{1.2}[^*B*_{2}] and
*F*_{1.3}[^*C*_{2}]

Now we will create a module M that depends all formulas: *M*[*F*_{1.0}, *G*_{1.0}, ...]. The claim is that iff there is a way to satisfy all dependencies of module *M*, then there is a solution to the wikipedia::3SAT formula.