Resolver and inefficiencies

[Jaroslav Tulach]

Dne Čt 3. května 2012 22:40:13, Paul Sandoz napsal(a):
> >> This observation may already be known, but i thought i would throw this
> >> out here anyway...> 
> > Yes, it's a known problem and the resolver needs work. There was an
> > interesting thread between Jaroslav Tulach and Jeff Glick a few months
> > ago on this topic.
> OK, i will look through the archives.

Hello Paul, the summary of my current understanding can be found here:
http://wiki.apidesign.org/wiki/RangeDependenciesAnalysed

Dne Čt 3. května 2012 17:03:40, Pascal Rapicault napsal(a):
> Rather than
> implementing a resolver from scratch, since the dependency problem is NP
> complete (I assume the jigsaw also is), 

Hello Pascal, the second part of the above link seems to indicate that the NP 
completeness can be avoided for compile time/linkage dependencies - if the 
repository is constructed in incremental fashion. 

I am not however afraid that including "require service" dependencies will 
change the game and make it NP-complete again - as it breaks the incremental 
creation condition. I have no idea right now how the "require service" problem 
could be made less complex.

> we have been using a SAT solver
> (http://www.sat4j.org) and have been quite happy with it. It is very
> efficient and scales very well.

If my above worry is correct, a SAT solver may be needed.
-jt