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