On Fri, Nov 02, 2007 at 05:23:53PM -0400, Micah Anderson wrote: > [...] formal proofs of the problem of migrating an > optimal set of packages to testing as a np-complete problem [...] Checking installability is an NP-complete problem. Proof: Installability of a package P from a set of packages S with dependency relationships D and conflict relationships C is defined as there being a subset I of S, P is in I, no two packages in I conflict, and the dependency relations of all packages in I are satsified by other packages in I. In order to prove this is NP, we show this is a subset of the SAT problem, which is known to be NP-complete. We do this by relating each package in S to a boolean that is true if the package is also in I, and false otherwise. We relate each dependency, p Depends: x | y | z, w to the logical statements: not(p) or x or y or z not(p) or w and each conflict, p Conflicts: x, y to the logical statements: not(p) or not(x) not(p) or not(y) and finally we indicate P should be in I: p Finding a solution via SAT for the truth value of each variable thus gives us a set I which satisfies all the requirements. So the installability is NP. To show installability is also NP-hard (and thus is NP-complete), we reduce 3SAT, which is know to be NP-hard, to an installability problem. 3SAT finds truth values for a set of variables, given expressions of the form: (x or y or z) where x, y and z are variables or their negations. Making the negations explicit gives only the following possibilities: (x or y or z) (!x or y or z) (!x or !y or z) (!x or !y or !z) In order to reduce this to an installability problem (expressed in terms of a set of packages, a package to be tested for installability, and a set of conflicts/depends relationships). As before, we relate each variable to a package, and its truth value to whether it is in the set I. We also introduce an additional package, P, and add a set of nega-packages Nx for each x. Each expression is converted as follows: (x or y or z) -> P Depends: x | y | z (!x or y or z) -> x Depends: y | z (!x or !y or z) -> x Depends: Ny | z (!x or !y or !z) -> P Depends: Nx | Ny | Nz In addition for each package x, Nx Conflicts: x. That gives a polynomial conversion of 3SAT to installability testing, proving correctness of the solution is left as an exercise to the reader (what did you think the margin to the left was for?). Since installability is both NP and NP-hard, it follows by definition, that it's NP-complete. Finding an optimal set of packages to move to testing is thus NP-hard (since it implies the solution to a bunch of NP-complete installability problems). I'm not sure if it's also NP though, but hey, I guess applicants have to have *something* left to prove, right? :) In any event, the current implementation is greedy (something goes into testing? add it!) rather than optimising (these three packages could go in, /or/ these four packages could), and tends to leave the hard problems to the RMs anyway, so "optimal" might be a bit misleading compared to reality. Cheers, aj
Attachment:
signature.asc
Description: Digital signature