Installability

Installability

As soon as we have conflict nodes, installability becomes NP-hard. We are not the first to remark this, see e.g.

From the linux.debian.devel list:

From: Anthony Towns
Date: 2000-07-19
Subject: Re: new fields in debian/control

On Wed, Jul 19, 2000 at 10:52:20AM +0200, Robert Bihlmeyer wrote:
> Branden Robinson  writes:
> > On Mon, Jul 17, 2000 at 02:33:34PM +0200, Adrian Bunk wrote:
> > > Successor-Of: including by me.  At one point I tried
> > to convince Jason Gunthorpe of it.  He started burning black candles, drew
> > a thaumaturgic circle around himself, and mumbled something about it making
> > the task apt's problem-resolver NP-complete.

(Really, apt's problem-resolver is already attacking something similar
to an NP-complete problem (I'm not sure if it is, or not, it's plausibly
harder; installability checking is NP-complete though). AIUI, apt gets
around this by some reasonably careful approximation)

> I can't really imagine why. Apt can ATM handle multiple versions of
> the same package pretty well. What will it matter in principle if
> these incarnations are not called foo-1.0 and foo-1.2, but foo-1.1 and
> bar-2.3?

They're not called foo-1.0 and foo-1.2, they're called foo, with version
numbers 1.0 and 1.2. You can only ever have one foo installed, but you can
have both foo and bar installed (conflicts aside) if you want. They're
different propositions. It's trivial to look up the successor to foo
1.0 at the moment: it's called foo, and it'll have a later version
number. Letting that be bar 2.3 as well would make that something of a
O(n) operation rather than an O(1) operation. What happens if both bar
2.3 and baz 4.5 are successors to foo? What does that mean? That you
should install one or the other, or that you should install both? What if
they conflict? What if two packages are successors of each other? What
if a foo 2.3 and bar 2.3 are both available, bar 2.3 succeeds foo <<
2.0 and foo 1.1 is installed? Do you choose foo? bar? Both? The one with
the higher priority? What if the new foo conflicts with something you've
already got installed? Do you switch to bar then?

I don't think any of the above questions are all that difficult to answer,
but if you're having difficulty coming up with questions in the first
place, well, maybe you just don't really understand what's involved.

Empirical complexity

The following graph shows the number of seconds required for solving installability using SAT formulaes produces by xlsat from the reference Debian pool, with two solvers : the Davis-Putnam solver written by Berke and sat-grasp?, as a function of the Oz source file size in bytes (this may not be very accurate). Time is in seconds. Curve-fitting in gnuplot? suggests that the behaviour is inherently quadratic for both solvers, sat-grasp? being faster by a factor of 10.