From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <avm@altlinux.ru>
Date: Sun, 17 Dec 2006 19:58:08 +0300
From: "Alex V. Myltsev" <avm@altlinux.ru>
To: devel@lists.altlinux.org
Message-ID: <20061217195808.1549f6c2@localhost.localdomain>
In-Reply-To: <20061217141247.GC6148@localhost.localdomain>
References: <20061011001636.GQ8008@localhost.localdomain>
	<20061207225233.GA14226@nomad.office.altlinux.org>
	<20061214234038.GH13476@localhost.localdomain>
	<20061215012503.GK13476@localhost.localdomain>
	<20061215222748.GE10215@basalt.office.altlinux.org>
	<20061215224259.GP13476@localhost.localdomain>
	<20061216120304.GA26551@hell.immo.ru>
	<20061216201925.GS13476@localhost.localdomain>
	<20061216210222.GB8977@basalt.office.altlinux.org>
	<20061217135150.GA18013@hell.immo.ru>
	<20061217141247.GC6148@localhost.localdomain>
X-Mailer: Sylpheed-Claws 2.3.1cvs20 (GTK+ 2.10.6; i586-alt-linux-gnu)
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Subject: Re: [devel] apt virtual packages
X-BeenThere: devel@lists.altlinux.org
X-Mailman-Version: 2.1.9rc1
Precedence: list
Reply-To: ALT Devel discussion list <devel@lists.altlinux.org>
List-Id: ALT Devel discussion list <devel.lists.altlinux.org>
List-Unsubscribe: <https://lists.altlinux.org/mailman/listinfo/devel>,
	<mailto:devel-request@lists.altlinux.org?subject=unsubscribe>
List-Archive: <http://lists.altlinux.org/pipermail/devel>
List-Post: <mailto:devel@lists.altlinux.org>
List-Help: <mailto:devel-request@lists.altlinux.org?subject=help>
List-Subscribe: <https://lists.altlinux.org/mailman/listinfo/devel>,
	<mailto:devel-request@lists.altlinux.org?subject=subscribe>
X-List-Received-Date: Sun, 17 Dec 2006 16:58:24 -0000
Archived-At: <http://lore.altlinux.org/devel/20061217195808.1549f6c2@localhost.localdomain/>
List-Archive: <http://lore.altlinux.org/devel/>
List-Post: <mailto:devel@altlinux.org>

On Sun, 17 Dec 2006 17:12:47 +0300
Alexey Tourbin wrote:
> Он там доказывает что в его модели проблема поиска оптимального
> решения NP-complete (это очень плохо по сложности).
Это в худшем случае очень плохо по сложности, а на практике может
отлично работать. Про это там дальше хорошо написано, см. раздел 
"Don't panic".

> Доказывает по
> аналогии с CNF-SAT, а как это доказывается для CNF-SAT я не знаю,
> поэтому ничего не понял.
1) Обычно NP-полноту задачи выполнимости КНФ доказывают, строя сведение
к ней для любой задачи из NP. Рассказать в общих чертах или offtopic?
2) Доказательство там не "по аналогии" с ВЫП, а сведением ВЫП к задаче
существования корректной установки. Знать доказательство NP-полноты ВЫП
здесь не нужно, достаточно помнить факт.