I found an interesting paper that seems to suggest it is in NP. >From the European Association of Software Science and Technology, March 2006:
by Roberto Di Cosmo, Berke Durak, Xavier Leroy, Fabio Mancinelli, Jerome Vouillon: Maintaining large software distributions: new challenges from the FOSS era. It[1] says: Theorem 1 (Package installability is an NP-complete problem). Checking whether a single package P can be installed, given a repository R, is NP-complete. It seems to apply to Debian. Best regards, Rudi [1]: http://www.easst.org/newsletter/toc/index.html#12 On Nov 13, 2007 8:18 PM, Anthony Towns <[EMAIL PROTECTED]> wrote: > 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 > > > -----BEGIN PGP SIGNATURE----- > > iD8DBQFHOncvOxe8dCpOPqoRAs9vAKCS+3X87F1BvtKRP3mzN0vly1nbkQCfWCO6 > zxD5eX2jttNk/+TCLcW6rK0= > =R2PF > -----END PGP SIGNATURE----- > > -- "We can try to do it by breaking free of the mental prison of separation and exclusion and see the world in its interconnectedness and non-separability, allowing new alternatives to emerge." -- after Vandana Shiva -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
