# LibraryReExportIsNPComplete

### From APIDesign

(Fixing unclosed <math> problem) |
(→Module Dependencies Problem) |
||

Line 17: | Line 17: | ||

Let <math>A_1, A_{1.1}, A_{1.7}, A_{1.11}</math> denote compatible versions of API <math>A</math>. | Let <math>A_1, A_{1.1}, A_{1.7}, A_{1.11}</math> denote compatible versions of API <math>A</math>. | ||

- | Let <math>A_1, | + | Let <math>A_1, A_{2.0}, A_{3.1}</math> denote incompatible versions of API <math>A</math>. |

- | Let | + | 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 | + | Let <math>A_{x.y} \rightarrow \Uparrow 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 '''Repository''' be any set of modules, their version and their dependencies on other modules with or without re-export. | Let '''Repository''' be any set of modules, their version and their dependencies on other modules with or without re-export. |

## Revision as of 20:21, 19 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 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 **Repository** be any set of modules, their version and their dependencies on other modules with or without re-export.

Let *M*_{x.y}[...] is a module in some repository of other modules with dependencies. Its dependencies are satisfied, if for each of modules it depends on is present in a compatible version with the requested version.

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.