[Hackage] #500: develop a tool to find the maximal consistent set of hackage packages

[Hackage]

#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