# LibraryReExportIsNPComplete

### From APIDesign

(→wikipedia::3SAT) |
(→Module Dependencies Problem) |
||

Line 13: | Line 13: | ||

== Module Dependencies Problem == | == Module Dependencies Problem == | ||

- | Let A, B, C, ... | + | Let <math>A, B, C, ...</math> denote an API. |

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

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

Let ''A''<sub>x.y</sub>[''B''<sub>u.v</sub>] denote the fact that version ''x.y'' of API A depends on version ''u.v'' of API ''B''. | Let ''A''<sub>x.y</sub>[''B''<sub>u.v</sub>] denote the fact that version ''x.y'' of API A depends on version ''u.v'' of API ''B''. |

## Revision as of 21:32, 18 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* < *m**a**t**h* > .*L**e**t* < *m**a**t**h* > *A*_{1},*A*_{2},*A*_{3.1} denote incompatible versions of API *A*.

Let *A*_{x.y}[*B*_{u.v}] denote the fact that version *x.y* of API A depends on version *u.v* of API *B*.

Let *A*_{x.y}[^*B*_{u.v}] denote the fact that version *x.y* of API A depends on version *u.v* of API *B* and that it 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.