On Sun, Dec 17, 2006 at 12:02:22AM +0300, Dmitry V. Levin wrote:
> On Sat, Dec 16, 2006 at 11:19:25PM +0300, Alexey Tourbin wrote:
> > On Sat, Dec 16, 2006 at 03:03:05PM +0300, Alexey I. Froloff wrote:
> > > * Alexey Tourbin <at@> [061216 01:48]:
> > > > В общем апт не должен ставить пакеты подряд.  А для каждого пакета
> > > > подряд он должен выделять подмножество пакетов удовлетворяющих условию.
> > > > А на втором проходе из этих подмножеств выделять одно непротиворечивое
> > > > множество которое подлежит установке.
> > > 
> > > http://people.debian.org/~dburrows/model.pdf
> > > Правда я этот резольвер оторвал, потому как глючный дюже...
> > 
> > Спасибо!  Я как раз думал, что это математическая задача.  То есть нужно
> > предложить конечный набор (последовательность) правил, как минимум для
> > install, а лучше ещё и для dist-upgrade, и желательно без весов.  То
> > есть чисто на теории множеств + исчислении предикатов, без чисел.
> 
> Я не верю что это можно сделать в общем случае, поскольку иногда решений
> более одного.

В одном частном случае, когда решений больше одного, это называется
shift/reduce conflict.  Автоматы обходятся без чисел (без весов), это
фундаментальное.