[devel] apt virtual packages

[Alexey Tourbin]

On Sun, Dec 17, 2006 at 04:51:50PM +0300, Alexey I. Froloff wrote:
> * Dmitry V. Levin <ldv@> [061217 00:13]:
> > > > http://people.debian.org/~dburrows/model.pdf
> > > > Правда я этот резольвер оторвал, потому как глючный дюже...
> > Я не верю что это можно сделать в общем случае, поскольку иногда решений
> > более одного.
> Да.  И aptitude предлагает все эти решения пользователю.  Только
> у меня этот резольвер вываливался на ассертах :-(

Он там доказывает что в его модели проблема поиска оптимального решения
NP-complete (это очень плохо по сложности).  Доказывает по аналогии с
CNF-SAT, а как это доказывается для CNF-SAT я не знаю, поэтому ничего
не понял.  В общем на будущее надо скачивать книжку Papadimitriou
Computational Complexity, может у кого-нибудь уже есть?
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 189 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20061217/e5f0576f/attachment-0001.bin>