From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id 6C8A0138350 for ; Sun, 26 Apr 2020 15:05:33 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 19AA0E0A88; Sun, 26 Apr 2020 15:05:28 +0000 (UTC) Received: from smtp.gentoo.org (dev.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id A5600E0A60 for ; Sun, 26 Apr 2020 15:05:27 +0000 (UTC) Subject: Re: [gentoo-user] Is Gentoo dead? To: gentoo-user@lists.gentoo.org References: <20200421165803.GB187193@redacted> <11506562.O9o76ZdvQC@peak> <20200421190145.GF187193@redacted> <0d270fdf-1de2-03b4-1f5a-702450975561@gmail.com> <2b6a7f82-b4c2-2115-e4e5-2ec27482a4c9@gentoo.org> From: Michael Orlitzky Message-ID: <0126669e-c207-8bed-f1d0-5ae81f55b2a0@gentoo.org> Date: Sun, 26 Apr 2020 11:05:21 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.6.0 Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-user@lists.gentoo.org Reply-to: gentoo-user@lists.gentoo.org X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-Archives-Salt: 5409fb96-46cc-4807-81bd-52c3589333a6 X-Archives-Hash: 5de1a488a9b0a42cbb5079f042391e2c On 4/26/20 10:23 AM, Caveman Al Toraboran wrote: >> >> 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. > I think something like this is the right approach in the long run. Right now, portage is using a bunch of heuristics in a totally unprincipled way to find a solution that works. If we can turn the dependency resolution problem into some abstract mathematical form, then solving it becomes "not our problem," and we can reap the benefits as new theoretical techniques are incorporated into the existing solvers (you wouldn't want to write your own).