On Sun, Dec 17, 2006 at 07:58:08PM +0300, Alex V. Myltsev wrote:
> 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?

Не оффтопик, но погодите.  Что такое КНФ я знаю хорошо, а что такое NP
я знаю хуже.  Нужно мне ещё самообразоваться.  Но сегодня выходной а
скоро будет новый год, борода из ваты, пьянь такая, и дел из-за синей
горы подвалило в общем ой.

Просто сейчас надо апт зафиксить чтобы он во всех типичных случаях всё
ставил как надо.  Кроме меня желающих нет я так понимаю.  Полиномиальная
трудность булевых функций это хорошо но пожалуй уже на следующий год.