On Tue, Nov 13, 2007 at 03:38:00PM -0500, Mike O'Connor wrote: > Anthony Towns writes: > >Checking installability is an NP-complete problem. Proof:
> The above proof by AJ seems to be a proof that figuring out if a single
> package is installable in testing is in NP, but doesn't say anything
> about installing an optimal set of pacakges in testing.
That's correct.
> I had no problem finding a reducability relationship that proves finding
> a optimal set of pacakges is NP-Hard. But I'm not finding a way to map
> a problem as a subset of problem in NP.
Hrm. An approach that might work:
- convert the optimisation problem to a decision problem
(is there a set of packages of size M from the N candidates
for testing that can be moved together into testing without
breaking anything?)
- expand the dependencies to deal with each version you're
actually considering, eg "foo Depends: bar" becomes "foo 1.0
Depends: bar 1.1 | bar 2.2"
- add statements to say you're not going to remove packages from
testing (ie, for each bar in testing, "bar-1.0-in-testing or
bar-1.1-in-testing" will be true)
- add statements to exclude multiple versions of the same package
being in testing (ie, "not bar-1.0-in-testing or not
bar-1.1-in-testing" will be true).
- figure out some way of saying M of the N "bar-1.1-in-testing,
baz-3.4-in-testing, ..." are true in an NP way
Cheers,
aj
signature.asc
Description: Digital signature
