LibraryReExportIsNPComplete

From APIDesign

(Difference between revisions)
Jump to: navigation, search
(→Module Dependencies Problem)
(Definition of the problem)
Line 31: Line 31:
:Let there be two chains of re-exported dependencies <math>A_{p.q} \gg ... \gg B_{x.y}</math> and <math>A_{p.q} \gg ... \gg B_{u.v}</math>, then <math>x = u \vee y = v</math>, this guarantees that each class has just one, exact meaning for each importer
:Let there be two chains of re-exported dependencies <math>A_{p.q} \gg ... \gg B_{x.y}</math> and <math>A_{p.q} \gg ... \gg B_{u.v}</math>, then <math>x = u \vee y = v</math>, this guarantees that each class has just one, exact meaning for each importer
-
 
+
'''Module Dependency Problem''': Let there be a repository <math>R=(M,D)</math> and a module <math>A \in M</math>. Does there exist a configuration <math>C</math> in the repository <math>R</math>, such that the module <math>A \in C</math>, e.g. the module can be enabled?
-
Let <math>Dep_R(A_{x.y})</math> be set of all modules in repository <math>R</math> that M depends on directly. E.g.
+
-
<math>Dep_R(A_{x.y}) = { B_{u.v} : A_{x.y} \rightarrow B_{u.v} \wedge
+
-
A_{x.y} \rightarrow B_{u.v} }</math>.
+
-
 
+
-
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 ==
== Converstion of [[wikipedia::3SAT]] to Module Dependencies Problem ==

Revision as of 10:02, 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:

(x_{11} \wedge x_{12} \wedge x_{13}) \vee
(x_{21} \wedge x_{22} \wedge x_{23}) \vee
(x_{31} \wedge x_{32} \wedge x_{33}) \vee
...
(x_{n1} \wedge x_{n2} \wedge x_{n3})

where each xab is a variable vi or a negation of a variable \neg v_i. 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 A_{x.y} \gg B_{u.v} 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 C \subseteq M, where following is satisfied:

\forall A_{x.y} \in C, \forall A_{x.y} \gg B_{u.v} \in D \Rightarrow \exists w >= v \vee B_{u.w} \in C, each dependency satisfied with some compatible version
\forall A_{x.y} \in C, \forall A_{x.y} > B_{u.v} \in D \Rightarrow \exists w >= v \vee B_{u.w} \in C, each dependency satisfied with some compatible version
Let there be two chains of re-exported dependencies A_{p.q} \gg ... \gg B_{x.y} and A_{p.q} \gg ... \gg B_{u.v}, then x = u \vee y = v, 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 A \in M. Does there exist a configuration C in the repository R, such that the module A \in C, e.g. the module can be enabled?

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.

Retrieved from "http://wiki.apidesign.org/wiki/LibraryReExportIsNPComplete"
Personal tools
buy