Comments | thesz: А вот кому разложение на множители?

thesz

А вот кому разложение на множители?

Nov 14, 2006 19:24

( на таблицах решений, само собой, NP-полное, но всё же! )

Comments 6

anonymous November 14 2006, 17:28:06 UTC

Чорт, пришел со встречи с дизайнерами, читал-читал, потом только вспомнил, что это charity - вышло примерно как тут http://community.livejournal.com/ru_stupid/27815.html

thesz November 14 2006, 17:34:13 UTC

Nope. This is Haskell. ;)

lomeo November 14 2006, 19:50:19 UTC

Пара вопросов - что такое sat и что за багу искал?
Ну, и чтобы придраться (а как же без этого!)

\(a,b) -> bvadd a b => uncurry bvadd

thesz November 14 2006, 21:14:11 UTC

Бага вот такая - scavenge_mark_stack.

В общем, наша программа вызывала её достаточно часто. Вот и выясняли.

Выяснили. Оказалось, что это происходит при уплотнении (compaction) кучи, если сборка накладывается каким-то образом на вывод информации. Если задать ключик +RTS -c, то она вылетает практически сразу. Я и пытался сделать что-то считающую программу, чтобы воспроизвести этот баг.

SAT - поиск CNF satisfaction set, набора значений переменных, который при подстановке в заданную конъюнктивную нормальую форму делает её истинной.

Для x & ~y этот набор x=1 и y=0.

К этой задаче сводятся все другие NP-полные задачи.

Да, с curry/uncurry я знаком плохо. Пока плохо. ;)

lomeo November 14 2006, 23:01:43 UTC

Плохо. Как нибудь обошли багу?
За SAT спасибо, не знал.

thesz November 14 2006, 23:21:13 UTC

Обошли, я думаю. Надеюсь. Завтра увижу. ;)

Отключили уплотнение ключиком +RTS -c100 - уплотнять при зполненности кучи на 100 процентов (чего не бывает никогда).

Забыл сказать про SAT. Если CNF состоит только из дизъюнкций по два элемента (SAT-2, по-моему, это называется), то её можно решить за полиномиальное время. Все остальные случаи уже NP-полны.

PS
Хочу попробовать подключить jhc. ;)