LibraryReExportIsNPComplete
From APIDesign
(→Converstion of wikipedia::3SAT to Module Dependencies Problem) |
|||
Line 57: | Line 57: | ||
'''Claim''': There <math>\exists</math> a configuration <math>C</math> of repository <math>R</math> and <math>T_{1.0} \in C</math> <math>\Longleftrightarrow</math> there is a solution to the [[wikipedia::3SAT]] formula. | '''Claim''': There <math>\exists</math> a configuration <math>C</math> of repository <math>R</math> and <math>T_{1.0} \in C</math> <math>\Longleftrightarrow</math> there is a solution to the [[wikipedia::3SAT]] formula. | ||
+ | |||
+ | == Proof == | ||
+ | |||
+ | "<math>\Leftarrow</math>": Let's have an evaluation of each variable to either true or false that evaluates the whole [[wikipedia::3SAT]] formula to true. Then <math>C = { T_{1.0} } \bigcup { M^i_{1.0} : v_i } \bigcup {M^i_{2.0} : \neg v_i } \bigcup { F^i_{1.1} : x_{i1} } \bigcup { F^i_{1.2} : \neg x_{i1} \vee x_{i2} } \bigcup { F^i_{1.3} : \neg x_{i1} \vee \neg x_{i2} \vee x_{i3} }</math> |
Revision as of 10:51, 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.
Contents |
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 xab is a variable vi or a negation of a variable . Each variable vi can appear multiple times in the expression.
Module Dependencies Problem
Let A,B,C,... denote an API.
Let A1,A1.1,A1.7,A1.11 denote compatible versions of API A.
Let A1,A2.0,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 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 v1,...,vm as defined above.
Let's create a repository of modules R. For each variable vi let's create two modules and , which are mutually incompatible and put them into repository R.
For each formula let's create a module Fi 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 T1.0 that depends all formulas:
- ...
and add 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.
Proof
"": Let's have an evaluation of each variable to either true or false that evaluates the whole wikipedia::3SAT formula to true. Then