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,
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.
Best regards,
Rudi
[1]: http://www.easst.org/newsletter/toc/index.html#12
On Nov 13, 2007 8:18 PM, Anthony Towns <aj@azure.humbug.org.au> 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
>
> Cheers,
> aj
>
>
> -----BEGIN PGP SIGNATURE-----
>
> iD8DBQFHOncvOxe8dCpOPqoRAs9vAKCS+3X87F1BvtKRP3mzN0vly1nbkQCfWCO6
> zxD5eX2jttNk/+TCLcW6rK0=
> =R2PF
> -----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
Vandana Shiva
Reply to: