<div dir="ltr">On 15 April 2015 at 11:15, David Cournapeau <span dir="ltr"><<a href="mailto:cournape@gmail.com" target="_blank">cournape@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote">This is indeed the case. If you want to solve dependencies in a way that works well, you want an index that describes all your available package versions.<div><br></div><div>While solving dependencies is indeed NP complete, they can be fairly fast in practice because of various specificities : each rule is generally only a few variables, and the rules have a specific form allowing for more efficient rule representation (e.g. "at most one of variable", etc...). In my experience, it is not more difficult than using graph-based algorithms, and</div><div><br></div><div>FWIW, at Enthought, we are working on a pure python SAT solver for resolving dependencies, to solve some of those issues. I am actually hacking on it right at PyCon, we hope to have a first working version end of Q2, at which point it will be OSS, and reintegrated in my older project depsolver (<a href="https://github.com/enthought/depsolver" target="_blank">https://github.com/enthought/depsolver</a>).</div><span class="HOEnZb"><font color="#888888"><div><br></div><div></div></font></span></div></div></div></blockquote><div><br></div><div>Awesome! Then pip could use that in the near future :)<br></div></div></div></div>