Re: [gentoo-user] Is Gentoo dead?

[Michael Orlitzky <mjo@gentoo.org>]

On 4/23/20 2:14 PM, Caveman Al Toraboran wrote:
> On Wednesday, April 22, 2020 9:34 PM, Michael Orlitzky <mjo@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.