[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Checking installability is an NP-complete problem

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

Reply to: