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

Re: Checking installability is an NP-complete problem

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


Attachment: signature.asc
Description: Digital signature

Reply to: