[Hackage] #500: develop a tool to find the maximal consistent
set of hackage packages
Hackage
trac at galois.com
Sun Feb 15 06:35:08 EST 2009
#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
More information about the cabal-devel
mailing list