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