*To*: debian-newmaint@lists.debian.org*Subject*: Checking installability is an NP-complete problem*From*: Mike O'Connor <stew@vireo.org>*Date*: Tue, 13 Nov 2007 15:38:00 -0500*Message-id*: <[🔎] 20071113203800.GK10966@catfish.vireo.org>*In-reply-to*: <[🔎] 20071103035133.GA24107@blae.erisian.com.au>

Anthony Towns writes: >Checking installability is an NP-complete problem. Proof: > > Installability of a package P from a set of packages S with dependency > relationships D and conflict relationships C is defined as there > being a subset I of S, P is in I, no two packages in I conflict, > and the dependency relations of all packages in I are satsified by > other packages in I. > > In order to prove this is NP, we show this is a subset of the SAT > problem, which is known to be NP-complete. We do this by relating each > package in S to a boolean that is true if the package is also in I, and > false otherwise. We relate each dependency, > > p Depends: x | y | z, w > > to the logical statements: > > not(p) or x or y or z > not(p) or w > > and each conflict, > > p Conflicts: x, y > > to the logical statements: > > not(p) or not(x) > not(p) or not(y) > > and finally we indicate P should be in I: > > p > > Finding a solution via SAT for the truth value of each variable > thus gives us a set I which satisfies all the requirements. So the > installability is NP. > 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. 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. Am i correct about this, or am I missing something? thanks, stew

**Attachment:
signature.asc**

**Follow-Ups**:**Re: Checking installability is an NP-complete problem***From:*Anthony Towns <aj@azure.humbug.org.au>

**References**:**Re: Miriam Ruiz advocation***From:*Anthony Towns <aj@azure.humbug.org.au>

- Prev by Date:
**Re: AM report for Cyril Brulebois (fwd)** - Next by Date:
**Re: Checking installability is an NP-complete problem** - Previous by thread:
**Re: Miriam Ruiz advocation** - Next by thread:
**Re: Checking installability is an NP-complete problem** - Index(es):