On 4/23/20 2:14 PM, Caveman Al Toraboran wrote:
> On Wednesday, April 22, 2020 9:34 PM, Michael Orlitzky <m...@gentoo.org>
> wrote:
>
>> Dependency resolution is indeed a (formally) hard problem. Solving the
>> traveling salesman problem is also hard. Solving the traveling salesman
>> problem while being punched in the face is even harder. When I complain
>> about portage being slow, what I mean is that I want to stop being
>> punched in the face so that I can concentrate all of my energy on the
>> underlying hard problem.
>
> any reason why is it a traveling salesman problem,
> and not just a tree walk with heuristics to handle
> exceptions (e.g. cycles)?
>
It's not outwardly a traveling salesman problem, but it's on the same
level of difficulty. If you look at RDEPEND in an ebuild, you'll see a
bunch of entries like
cat/pkg <= version
As the package manager recursively processes all of the ebuilds in the
dependency graph, you wind up with a goal like
maximize the versions of all installed packages
subject to
cat/pkg1 <= version1
cat/pkg1 > version2
cat/pkg2 >= version3
...
That looks a lot like a linear programming problem, but package versions
are discrete. So ignoring all of the details, it's believable that we
have an integer programming problem, which is NP-complete.
