From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gentoo-user+bounces-190829-garchives=archives.gentoo.org@lists.gentoo.org>
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 C1F89138350
	for <garchives@archives.gentoo.org>; Fri, 24 Apr 2020 21:23:46 +0000 (UTC)
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
	by pigeon.gentoo.org (Postfix) with SMTP id D531AE0887;
	Fri, 24 Apr 2020 21:23:40 +0000 (UTC)
Received: from smtp.gentoo.org (smtp.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 79556E086A
	for <gentoo-user@lists.gentoo.org>; Fri, 24 Apr 2020 21:23:40 +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>
 <qAzDBjufBr6-8U56hSdh1xt-9m2WcLChbQxMW0tgORKHud3NveUS7cPlDmwfufFFqsXurYaJwEjEog7l4C6Elq9FB1JM0VjcYfvXAjAasLA=@protonmail.com>
 <b8a13138-aa97-858a-f0dc-91a378e86a2f@gentoo.org>
 <0d270fdf-1de2-03b4-1f5a-702450975561@gmail.com>
 <2b6a7f82-b4c2-2115-e4e5-2ec27482a4c9@gentoo.org>
 <eYhXUgDPoa0-EevywBCaJUhcruxdqZm0r8Nkm9EnuWYvB0DBqeyF5gs1MeueUHRDiPv7cVEVmViTlqwmDPli7-GsjZ9p4mLkDugKBkvOCPc=@protonmail.com>
From: Michael Orlitzky <mjo@gentoo.org>
Message-ID: <af56ecf6-7607-efd2-78fb-c46ff03a9641@gentoo.org>
Date: Fri, 24 Apr 2020 17:23:36 -0400
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.6.0
Precedence: bulk
List-Post: <mailto:gentoo-user@lists.gentoo.org>
List-Help: <mailto:gentoo-user+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-user+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-user+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-user.gentoo.org>
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: <eYhXUgDPoa0-EevywBCaJUhcruxdqZm0r8Nkm9EnuWYvB0DBqeyF5gs1MeueUHRDiPv7cVEVmViTlqwmDPli7-GsjZ9p4mLkDugKBkvOCPc=@protonmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
X-Archives-Salt: 86f0ba4b-318f-4f44-8616-f68896c29898
X-Archives-Hash: 56d97361c8399348511db687ffc728d9

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.