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
Description: Digital signature