On Wed, Nov 14, 2007 at 05:09:25AM +0000, Rudi Cilibrasi wrote: > 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. of course it does, this was written during the EDOS project, and it generated tools like edos-debcheck that derive from the concepts in this (and other) papers. -- ·O· Pierre Habouzit ··O madcoder@debian.org OOO http://www.madism.org
Attachment:
pgpz1gd_xnzWm.pgp
Description: PGP signature