On Saturday, April 25, 2020 1:23 AM, Michael Orlitzky <m...@gentoo.org> wrote:
> 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. i'm dumb, and don't fully understand this, but i think i found something interesting: [1] http://www.aimsciences.org/article/doi/10.3934/jimo.2014.10.557 i wonder, can gradient descent be used to find optimal portage solution? didn't read beyond the abstract in [1], but from the abstract it seems doable (i.e. integer programming solvable by gradient descent). anyone please correct me if i'm wrong. if doing it with gradient descent is doable, then i wonder, can emerge one day be GPU accelerated? how coold would it be? :D ``world's 1st GPU accelerated package manager''! of course it is not a pressing issue, but i think it is a very fun puzzle to think about in my free time (which is most of my life these days), and i think some here may like contemplating such shameless thoughts. rgrds, cm.
