# LibraryReExportIsNPComplete

### From APIDesign

(→Converstion of wikipedia::3SAT to Module Dependencies Problem) |
(→wikipedia::3SAT) |
||

Line 4: | Line 4: | ||

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: | 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: | ||

- | :<math>(x_{11} \ | + | :<math>(x_{11} \vee x_{12} \vee x_{13}) \wedge </math> |

- | :<math>(x_{21} \ | + | :<math>(x_{21} \vee x_{22} \vee x_{23}) \wedge </math> |

- | :<math>(x_{31} \ | + | :<math>(x_{31} \vee x_{32} \vee x_{33}) \wedge </math> |

:<math>...</math> | :<math>...</math> | ||

- | :<math>(x_{n1} \ | + | :<math>(x_{n1} \vee x_{n2} \vee x_{n3})</math> |

where each <math>x_{ab}</math> is a variable <math>v_i</math> or a negation of a variable <math>\neg v_i</math>. Each variable <math>v_i</math> can appear multiple times in the expression. | where each <math>x_{ab}</math> is a variable <math>v_i</math> or a negation of a variable <math>\neg v_i</math>. Each variable <math>v_i</math> can appear multiple times in the expression. | ||

## Revision as of 10:34, 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 *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 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* *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 is satisfied:

- - each re-exported dependency is satisfied with some compatible version
- - each dependency is satisfied with some compatible version
- Let there be two chains of re-exported dependencies and then - this guarantees that each class has just one, exact meaning for each importer

**Module Dependency Problem**: Let there be a repository *R* = (*M*,*D*) and a module . Does there exist a configuration *C* in the repository *R*, such that the module , e.g. the module can be enabled?

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

Let there be wikipedia::3SAT formula with with variables *v*_{1},...,*v*_{m} as defined above.

Let's create a repository of modules *R*. For each variable *v*_{i} let's create two modules and , which are mutually incompatible and put them into repository *R*.

For each formula
let's create a module *F*^{i} that will have three compatible versions. Each of them will depend on one variable's module. In case the variable is used with negation, it will depend on version *2.0*, otherwise on version *1.0*. So for the formula

we will get:

All these modules and dependencies add into repository *R*

Now we will create a module *T*_{1.0} that depends all formulas:

...

and this module as well as its dependencies into repository *R*.

**Claim**: There a configuration *C* of repository *R* and there is a solution to the wikipedia::3SAT formula.