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

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,


[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
> iD8DBQFHOncvOxe8dCpOPqoRAs9vAKCS+3X87F1BvtKRP3mzN0vly1nbkQCfWCO6
> zxD5eX2jttNk/+TCLcW6rK0=
> =R2PF

"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: