RangeDependenciesNP

From APIDesign

From the things described so far it seems that RangeDependencies may not be as bad, but still, there are severe NP-Complete problems associated with them. Following sections demonstrate the problems.

Module Repository with Ranges

Let Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/603461a02a54d311299bbe0f2ee2fd57.png , , /var/www/apidesign/httpdocs): A, B, C, ...

denote various modules and their APIs.

Let Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/76eadc2672277c83beedb27845ac3d5f.png , , /var/www/apidesign/httpdocs): A_{1.0}, A_{1.1}, A_{1.7}, A_{1.11}, A_{2.1}, A_{2.9}, A_{3.0}

denote versions of module Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/7fc56270e7a70fa81a5935b72eacbe29.png  ,  , /var/www/apidesign/httpdocs): A

. It is not really important what format the versions use, the only condition is that there is a linear order among the versions. As such the rest of the terminology is using single variable (Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/9dd4e461268c8034f5c8564e155c67a6.png , , /var/www/apidesign/httpdocs): x

or Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/83878c91171338902e0fe0fb97a8c47a.png  ,  , /var/www/apidesign/httpdocs): p

) to denote the version.

Let Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/f8b0db5505da6c2e0b78349ed94396ba.png , , /var/www/apidesign/httpdocs): A_{x} \rightarrow B_{[u,v)}

denote the fact that version x of module A depends on version range Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/ec8464c3339b191bb6816f09ff05f2e4.png  ,  , /var/www/apidesign/httpdocs): [u, v)
of module B. E.g. any version of module B between u and less than v can be used to satisfy A's need. Let Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/727583d093b7fd0618671f0fa9703a88.png  ,  , /var/www/apidesign/httpdocs): A_{x} \rightarrow B_{[u,v]}
denote closed interval dependency and allow its usage as well. 

Let Repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/5f0c2abe81264bb793e9c277e5d23a42.png , , /var/www/apidesign/httpdocs): R=(M,D)

be any set of modules with their versions and their dependencies on other modules.

Let C be a Configuration in a repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/5f0c2abe81264bb793e9c277e5d23a42.png , , /var/www/apidesign/httpdocs): R=(M,D) , if Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/ccb62089b190b0fbd045249cbcd47fc9.png , , /var/www/apidesign/httpdocs): C \subseteq M , where following is satisfied:

1. each dependency is satisfied with some version from dependency range: Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/04630f7f33791ba4e2ba66ae9ab1b269.png , , /var/www/apidesign/httpdocs): \forall A_x \in C, \forall A_x \rightarrow B_{[u,v)} \in D \Rightarrow \exists w \in [u,v) \wedge B_{w} \in C

1. only one version is enabled: Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/96f31d4596aa0a595b43893073271532.png , , /var/www/apidesign/httpdocs): A_{x} \in C \wedge A_{y} \in C \Rightarrow x = y

Module Range Dependency Problem

Let there be a repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/2c96ee8455bb0b58b09ea73bf8d9717a.png , , /var/www/apidesign/httpdocs): R = (M,D)

and a module Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/4cfccc68f6f2a85824f1e2aa908a72a2.png  ,  , /var/www/apidesign/httpdocs): A \in M

. Does there exist a configuration Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/0d61f8370cad1d412f80b84d143e1257.png , , /var/www/apidesign/httpdocs): C

in the repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/e1e1d3d40573127e9ee0480caf1283d6.png  ,  , /var/www/apidesign/httpdocs): R

, such that the module Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/21b399ddb43f8c61fbea617b595cba1b.png , , /var/www/apidesign/httpdocs): A \in C , e.g. the module can be enabled?

Conversion of 3SAT to Module Range Dependencies Problem

Let there be 3SAT formula with variables Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/8d70b5d26b99f566646b0538598fa174.png , , /var/www/apidesign/httpdocs): v_1, ..., v_m

as defined at in the original proof.

Let's create a repository of modules Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/e1e1d3d40573127e9ee0480caf1283d6.png , , /var/www/apidesign/httpdocs): R . For each variable Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/1df181eaa1bb40a0067c06ead197170d.png , , /var/www/apidesign/httpdocs): v_i

let's create two modules Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/7f452842ac00f6d3f3eb60578b77bd23.png  ,  , /var/www/apidesign/httpdocs): M^i_{1.0}
and Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/080560cd1e1e08482185b477793cfe71.png  ,  , /var/www/apidesign/httpdocs): M^i_{1.1}

, and put them into repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/e1e1d3d40573127e9ee0480caf1283d6.png , , /var/www/apidesign/httpdocs): R .

For each formula Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/c1498563a9f700cb96cf7611298134e5.png , , /var/www/apidesign/httpdocs): (x_{i1} \vee x_{i2} \vee x_{i3})

let's create a module Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/28b67ea410229674c5d5d4a04a33a1d2.png , , /var/www/apidesign/httpdocs): F^i

that will have three versions. Each of them will depend on one variable's module. In case the variable is used with negation, it will depend on version 1.0, otherwise on version 1.1. So for formula 

Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/803d7b7edeb63d092ecc88e132a263a2.png , , /var/www/apidesign/httpdocs): v_a \vee \neg v_b \vee \neg v_c

we will get:

Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/5fefb6a633c43cea3ddc4f6663c542d0.png , , /var/www/apidesign/httpdocs): F^i_{1.1} \rightarrow M^a_{[1.1,1.1]}

Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/0ee4901e54e9fcbcd21f8b8ac673bea6.png , , /var/www/apidesign/httpdocs): F^i_{1.2} \rightarrow M^b_{[1.0,1.0]}

Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/206c8ac84b354b3c1bd4d32192134cd1.png , , /var/www/apidesign/httpdocs): F^i_{1.3} \rightarrow M^c_{[1.0,1.0]}

All these modules and dependencies are added into repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/e1e1d3d40573127e9ee0480caf1283d6.png , , /var/www/apidesign/httpdocs): R

Now we will create a module Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/7eb58621dac37118dbc66c2dd1d086ed.png , , /var/www/apidesign/httpdocs): T_{1.0}

that depends on all formulas: 

Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/c61125c2aa50978795bebb0fe2a9f2e8.png , , /var/www/apidesign/httpdocs): T_{1.0} \rightarrow F^1_{[1.0,2.0)}

Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/0c4820949cfacdc00727bcc4103c260d.png , , /var/www/apidesign/httpdocs): T_{1.0} \rightarrow F^2_{[1.0,2.0)}

...

Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/c5fa5fc813be279fda805ad1776f5e6f.png , , /var/www/apidesign/httpdocs): T_{1.0} \rightarrow F^n_{[1.0,2.0)}

and add this module as well as its dependencies into repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/e1e1d3d40573127e9ee0480caf1283d6.png , , /var/www/apidesign/httpdocs): R .

Claim: There Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/39e0801f2d75bbab12f2e9b181658e1d.png , , /var/www/apidesign/httpdocs): \exists C

(a configuration) of repository Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/e1e1d3d40573127e9ee0480caf1283d6.png  ,  , /var/www/apidesign/httpdocs): R
and Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/89890f62c55c51677985649163abb4e4.png  ,  , /var/www/apidesign/httpdocs): T_{1.0} \in C
Failed to parse (math_image_error /var/www/apidesign/httpdocs/images/tmp/755eceba2d1c23fb97b1d4eb3a880058.png  ,  , /var/www/apidesign/httpdocs): \Longleftrightarrow
there is a solution to the 3SAT formula.

The proof is step by step similar to the one given in LibraryReExportIsNPComplete, so it is not necessary to repeat it here.