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 A6460139694 for ; Tue, 30 May 2017 08:47:14 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 1FC9AE0ECF; Tue, 30 May 2017 08:47:03 +0000 (UTC) Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id C434EE0ECA for ; Tue, 30 May 2017 08:47:02 +0000 (UTC) Received: from localhost (unknown [IPv6:2a01:e34:eeaa:6bd0:4ecc:6aff:fe03:1cfc]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: aballier) by smtp.gentoo.org (Postfix) with ESMTPSA id 115113416E2 for ; Tue, 30 May 2017 08:47:00 +0000 (UTC) Date: Tue, 30 May 2017 10:46:54 +0200 From: Alexis Ballier To: gentoo-dev@lists.gentoo.org Subject: Re: [gentoo-dev] [RFC] Forced/automatic USE flag constraints (codename: ENFORCED_USE) Message-ID: <20170530104654.31b89e10@gentoo.org> In-Reply-To: <20170530092245.681d4aeb@snowblower> References: <1496071993.31087.1.camel@gentoo.org> <20170529200037.2559f80a@gentoo.org> <1496093035.12795.3.camel@gentoo.org> <20170530094245.40e1cf64@gentoo.org> <20170530092245.681d4aeb@snowblower> Organization: Gentoo X-Mailer: Claws Mail 3.15.0-dirty (GTK+ 2.24.31; x86_64-pc-linux-gnu) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@lists.gentoo.org Reply-to: gentoo-dev@lists.gentoo.org MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Archives-Salt: f304c0dc-e0c9-44aa-857f-37248e5eb432 X-Archives-Hash: fc0c99cc82d56846c900d9a223067922 On Tue, 30 May 2017 09:22:45 +0100 Ciaran McCreesh wrote: > On Tue, 30 May 2017 09:42:45 +0200 > Alexis Ballier wrote: > > Oh crap, this requires to solve SAT. > > The main problem would not be solving SAT, in this case. The problem > is providing the right answer when not enough information is given. > Spitting out a resolution which satisfies every dependency isn't > typically that difficult. Spitting out a resolution which doesn't > just turn off all your use flags and uninstall most of your programs > is the hard part. I don't really understand here: Assuming the formula is reduced where user-set useflags and profile-masked/forced ones are already assigned their true/false values, this leaves a formula with variables where changing any of those won't turn off (or on) anything you didn't want. If you can solve SAT on this reduced instance then you're safe, aren't you ? > > Not hard as in you need a Ph.D. in algorithms to solve it but the > > kind of hardness almost every cryptographic algorithm used today, > > and in the foreseeable future, relies on. > > Hrm, you're a bit off, there. SAT solving in practice isn't usually > that bad unless either your inputs are huge or they're deliberately > crafted to be ultra-nasty. Being NP-complete just means that instances > that will hit exponential behaviour exist, not that those instances > will occur in the application area you care about. Yes, SAT is somewhat one of the easiest NP complete problems. Still, do we accept everyone having php installed to have its 'emerge -uDN world' consume 1 cpu-minute? 10 cpu-minutes? 60 cpu-minutes? What's the limit? How do we define 'ultra-nasty' constructs? How do we avoid them? Do we want to spec the solver's heuristic used so that developers can rely on it performing well on some constructs and poorly on some others? Do we want to spec some syntax so that PM developers can use an heuristic performing well on the instances provided? I really believe that's too many questions for something that can be solved efficiently in a simpler manner. Bests, Alexis.