#500: develop a tool to find the maximal consistent set of hackage packages ----------------------------+----------------------------------------------- Reporter: duncan | Owner: Type: enhancement | Status: new Priority: normal | Milestone: Component: miscellaneous | Version: Severity: normal | Resolution: Keywords: | Difficulty: project(> week) Ghcversion: | Platform: ----------------------------+----------------------------------------------- Comment (by duncan): Replying to [comment:1 michiexile]:
If we assume that we can have "installable with..." as a primitive operation (and package THAT instance of NP in there), then it should be easy to build a graph with vertices the packages and edges given by an edge package1 -- package2 precisely when there is some set of dependency fulfillment that is fulfilled by all of them.
Hmm, I'm not sure about this. Solutions do not combine easily here. Just because we can find a way to install package P1 and a way to install package P2 does not mean we can combine those solutions to make a solution for package P1 and P2. If we could then the problem would be polynomial. Perhaps I don't understand the algorithm you're presenting but it looks like it could also be used to solve the normal problem of package planning in polynomial time. That's a bit suspicious because we know that problem is NP-complete. Perhaps you can present the idea in more detail somewhere. -- Ticket URL: http://hackage.haskell.org/trac/hackage/ticket/500#comment:5 Hackage http://haskell.org/cabal/ Hackage: Cabal and related projects