From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gentoo-dev+bounces-80908-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 C48DA139694
	for <garchives@archives.gentoo.org>; Fri,  2 Jun 2017 15:10:24 +0000 (UTC)
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
	by pigeon.gentoo.org (Postfix) with SMTP id 19857E0DC0;
	Fri,  2 Jun 2017 15:10:14 +0000 (UTC)
Received: from blaine.gmane.org (unknown [195.159.176.226])
	(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 B18FCE0D6F
	for <gentoo-dev@lists.gentoo.org>; Fri,  2 Jun 2017 15:10:13 +0000 (UTC)
Received: from list by blaine.gmane.org with local (Exim 4.84_2)
	(envelope-from <lnx-gentoo-dev@m.gmane.org>)
	id 1dGoDD-0005lc-JQ
	for gentoo-dev@lists.gentoo.org; Fri, 02 Jun 2017 17:10:03 +0200
X-Injected-Via-Gmane: http://gmane.org/
To: gentoo-dev@lists.gentoo.org
From: Martin Vaeth <martin@mvath.de>
Subject: [gentoo-dev] Re: [RFC] Forced/automatic USE flag constraints (codename:
 ENFORCED_USE)
Date: Fri, 2 Jun 2017 15:09:57 +0000 (UTC)
Message-ID: <slrnoj2vub.vuq.martin@lounge.imp.fu-berlin.de>
References: <1496071993.31087.1.camel@gentoo.org>
 <20170529200037.2559f80a@gentoo.org> <1496093035.12795.3.camel@gentoo.org>
 <20170530094245.40e1cf64@gentoo.org> <20170530092245.681d4aeb@snowblower>
 <20170530104654.31b89e10@gentoo.org> <20170530095607.1adbc0b8@snowblower>
 <20170530112518.65b4f9e9@gentoo.org>
 <22829.24276.295.969060@a1i15.kph.uni-mainz.de>
 <1496154812.1238.5.camel@gentoo.org> <20170530173340.0b575526@gentoo.org>
 <1496167898.1335.1.camel@gentoo.org> <20170530204614.61e8e42c@gentoo.org>
 <1496213717.1164.1.camel@gentoo.org> <20170531093257.23b66f88@gentoo.org>
 <1496217792.1164.5.camel@gentoo.org> <20170531103819.417c2420@gentoo.org>
 <1496235892.25038.1.camel@gentoo.org> <20170531193922.477245bb@gentoo.org>
 <1496257344.25758.1.camel@gentoo.org> <20170601105523.08a9234e@gentoo.org>
 <1496352685.30502.4.camel@gentoo.org> <20170602132758.50a5f734@gentoo.org>
 <1496411717.29233.5.camel@gentoo.org>
Precedence: bulk
List-Post: <mailto:gentoo-dev@lists.gentoo.org>
List-Help: <mailto:gentoo-dev+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-dev+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-dev+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-dev.gentoo.org>
X-BeenThere: gentoo-dev@lists.gentoo.org
Reply-to: gentoo-dev@lists.gentoo.org
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Complaints-To: usenet@blaine.gmane.org
User-Agent: slrn/pre1.0.0-26 (Linux)
X-Archives-Salt: 7672db4a-f3fc-4dac-a58c-dd69a3a91839
X-Archives-Hash: 416847cbfcf2d56ba890fc4bd4e3f298

Michał Górny <mgorny@gentoo.org> wrote:
>   b? ( a ) c? ( b ) d? ( c ) e? ( d ) ...

As written in another posting: This is 2SAT.
2SAT is solvable in linear time.
To get a hard example you have to use several 3SAT clauses, i.e.
|| ( ... ) with 3 (or more) entries (and all of these entries must
occur in the other clauses, of course, to get a hard example).