[devel] apt virtual packages

[Alexey Tourbin]

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
я знаю хуже.  Нужно мне ещё самообразоваться.  Но сегодня выходной а
скоро будет новый год, борода из ваты, пьянь такая, и дел из-за синей
горы подвалило в общем ой.

Просто сейчас надо апт зафиксить чтобы он во всех типичных случаях всё
ставил как надо.  Кроме меня желающих нет я так понимаю.  Полиномиальная
трудность булевых функций это хорошо но пожалуй уже на следующий год.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 189 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20061217/027a9fcb/attachment-0001.bin>