On Sun, Dec 17, 2006 at 08:57:08PM +0300, Alex V. Myltsev wrote:
> On Sun, 17 Dec 2006 20:45:11 +0300
> Alexey Tourbin wrote:
> > Просто сейчас надо апт зафиксить чтобы он во всех типичных случаях всё
> > ставил как надо.
> > Полиномиальная трудность булевых функций это хорошо но пожалуй уже на
> > следующий год.
> Вооот. Из чего следует вывод: P там или NP, но задачу решать надо, а всё
> это доказательство в model.pdf было только для наукообразности.

Нет.  Это вовсе не из наукообразности в смысле чистоплюйства.
Предел практической вычислимости подступает к горлу довольно быстро.
Вот один дебилушка который реализовал продвинутый dependency solver пишет:

  One of the known issues in I've been trying to address in Smart for
  a while is the freezing effect that happens when a very complex
  upgrading situation (such as a full distribution upgrade) results in
  a combinatory explosion due to the number of choices to be
  analysed. Unfortunately, I never had time to really put in practice a
  reasonable solution for the problem. At this point, the beauty of
  open source software starts to shine.                                                                                                     
                                                                                                                                            
  A few weeks ago, Eran Tromer got close to the project and started
  researching and discussing about the issue. Not only that, but he
  produced actual patches that change the algorithm to prune the search
  space and find resonable solutions in acceptable timings. These
  patches were applied into the development version, and included in
  release 0.50rc1.                                                       
                                                                                                                                            
  The preliminary results are quite impressive. David Farning has
  tested Smart 0.50rc1 with Fedora in several situations, and reported:     
                                                                                                                                            
  fc4->fc5, fc4->fc6, fc4->devel, fc5->fc6, all calculate updates and
  upgrades in a few minutes on a vm with 512M, using standard repos +
  Freshrpms and Dries. Much quicker than with 0.42.                                                                                         

http://blog.labix.org

Несклько минут уходит на то, чтобы вычислить dist-upgrade на две тысячи
пакетов.  При том что никаких сложных переименований там на самом деле
нет, просто резольвер перебирает все-все-все возможные варианты.  А до
этого полчаса наверное обновление считал, и это преподносится как
большой успех!