*To*: "Rudi Cilibrasi" <cilibrar@gmail.com>, "Mike O'Connor" <stew@vireo.org>, aj@azure.humbug.org.au, debian-newmaint@lists.debian.org*Subject*: Re: Checking installability is an NP-complete problem*From*: "Rudi Cilibrasi" <cilibrar@gmail.com>*Date*: Wed, 14 Nov 2007 05:45:11 -0800*Message-id*: <[🔎] bd3cb4550711140545p7c63c7dew3b4fee8053f26c4@mail.gmail.com>*In-reply-to*: <[🔎] 20071114101059.GB18926@artemis.corp>*References*: <[🔎] 20071103035133.GA24107@blae.erisian.com.au> <[🔎] 20071113203800.GK10966@catfish.vireo.org> <[🔎] 20071114041855.GA9786@blae.erisian.com.au> <[🔎] bd3cb4550711132109w83d4a1bldaf886cdcac9c1c5@mail.gmail.com> <[🔎] 20071114101059.GB18926@artemis.corp>

Thanks for the background. As it turns out, approximating NP complete problems was one of the subjects of my research in the past seven years. The quartet tree program we wrote, the libqsearch program, is indeed solving an NP-complete problem (finding a best fitting binary tree) for a limitted size problem. In practical terms I usually find a simulated-annealing type approach, monte carlo method, or metropolis type algorithm gives a "good enough" solution in many real world cases. All of these phrases have been used to describe the libqsearch NP approximation system we wrote. I am happy to try to solve the Debian version approximately also (I usually choose STL + C++ for this kind of thing) but I do not understand the whole problem or background quite well enough to start it by myself yet. Cheers, -r. On Nov 14, 2007 2:10 AM, Pierre Habouzit <madcoder@debian.org> wrote: > 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 > -- "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

**References**:**Re: Miriam Ruiz advocation***From:*Anthony Towns <aj@azure.humbug.org.au>

**Checking installability is an NP-complete problem***From:*Mike O'Connor <stew@vireo.org>

**Re: Checking installability is an NP-complete problem***From:*Anthony Towns <aj@azure.humbug.org.au>

**Re: Checking installability is an NP-complete problem***From:*"Rudi Cilibrasi" <cilibrar@gmail.com>

**Re: Checking installability is an NP-complete problem***From:*Pierre Habouzit <madcoder@debian.org>

- Prev by Date:
**Re: Checking installability is an NP-complete problem** - Next by Date:
**Advocate DM: Jose Parrella** - Previous by thread:
**Re: Checking installability is an NP-complete problem** - Next by thread:
**Re: Miriam Ruiz advocation** - Index(es):