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, может у кого-нибудь уже есть?