Re: Checking installability is an NP-complete problem
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,
Maintaining large software distributions: new challenges from the FOSS era.
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.
On Nov 13, 2007 8:18 PM, Anthony Towns <email@example.com> 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
> -----BEGIN PGP SIGNATURE-----
> -----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