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
Attachment:
signature.asc
Description: Digital signature