[devel] apt virtual packages

[Alex V. Myltsev]

On Sun, 17 Dec 2006 17:12:47 +0300
Alexey Tourbin wrote:
> Он там доказывает что в его модели проблема поиска оптимального
> решения NP-complete (это очень плохо по сложности).
Это в худшем случае очень плохо по сложности, а на практике может
отлично работать. Про это там дальше хорошо написано, см. раздел 
"Don't panic".

> Доказывает по
> аналогии с CNF-SAT, а как это доказывается для CNF-SAT я не знаю,
> поэтому ничего не понял.
1) Обычно NP-полноту задачи выполнимости КНФ доказывают, строя сведение
к ней для любой задачи из NP. Рассказать в общих чертах или offtopic?
2) Доказательство там не "по аналогии" с ВЫП, а сведением ВЫП к задаче
существования корректной установки. Знать доказательство NP-полноты ВЫП
здесь не нужно, достаточно помнить факт.