LibraryReExportIsNPComplete
From APIDesign
| Line 9: | Line 9: | ||
where each ''x'' is a variable or a negation of a variable, and each variable can appear multiple times in the expression. | 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''<sub>1</sub>, ''A''<sub>1.1</sub>, ''A''<sub>1.7</sub>, ''A''<sub>1.11</sub> denotes compatible versions of API ''A''. | ||
| + | |||
| + | Let ''A''<sub>1</sub>, ''A''<sub>2</sub>, ''A''<sub>3.1</sub> denote incompatible versions of API ''A''. | ||
| + | |||
| + | 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'' 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''<sub>x.y</sub>[...] 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''<sub>a</sub> or ¬''x''<sub>b</sub> or ¬''x''<sub>c</sub>) and (''x''<sub>a</sub> or ''x''<sub>b</sub> or ''x''<sub>d</sub>) | ||
| + | be a formula. For each variable ''x''<sub>a</sub> let's create two modules with incompatible version ''A''<sub>1</sub> and ''A''<sub>2</sub> 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''<sub>a</sub> or ¬''x''<sub>b</sub> or ¬''x''<sub>c</sub>) | ||
| + | we will get: | ||
| + | ''F''<sub>1.1</sub>[^''A''<sub>1</sub>] and | ||
| + | ''F''<sub>1.2</sub>[^''B''<sub>2</sub>] and | ||
| + | ''F''<sub>1.3</sub>[^''C''<sub>2</sub>] | ||
| + | |||
| + | Now we will create a module M that depends all formulas: ''M''[''F''<sub>1.0</sub>, ''G''<sub>1.0</sub>, ...]. 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. | ||
Revision as of 01:48, 15 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:
- (x11 OR x12 OR x13) AND
- (x21 OR x22 OR x23) AND
- (x31 OR x32 OR x33) 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 A1, A1.1, A1.7, A1.11 denotes compatible versions of API A.
Let A1, A2, A3.1 denote incompatible versions of API A.
Let Ax.y[Bu.v] denote the fact that version x.y of API A depends on version u.v of API B.
Let Ax.y[^Bu.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 Mx.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 (xa or ¬xb or ¬xc) and (xa or xb or xd) be a formula. For each variable xa let's create two modules with incompatible version A1 and A2 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 (xa or ¬xb or ¬xc) we will get: F1.1[^A1] and F1.2[^B2] and F1.3[^C2]
Now we will create a module M that depends all formulas: M[F1.0, G1.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.
Follow
