[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, может у кого-нибудь уже есть?
----------- следущая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : отсутствует
Тип     : application/pgp-signature
Размер  : 189 байтов
Описание: отсутствует
Url     : http://lists.altlinux.org/pipermail/devel/attachments/20061217/e5f0576f/attachment.bin