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

Checking installability is an NP-complete problem

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?


Attachment: signature.asc
Description: Digital signature

Reply to: