Re: Checking installability is an NP-complete problem
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
Reply to: