# LibraryReExportIsNPComplete

### From APIDesign

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:

- (
*x*_{11}OR*x*_{12}OR*x*_{13}) AND - (
*x*_{21}OR*x*_{22}OR*x*_{23}) AND - (
*x*_{31}OR*x*_{32}OR*x*_{33}) AND ...

where each *x* is a variable or a negation of a variable, and each variable can appear multiple times in the expression.

## Module Dependencies Problem

Let A, B, C, ... denotes an API.

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

Let *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.