Список типичных NP-сложных задач, что именно обычно делает задачу NP-сложной, и что это на самом деле означает, пожалуй, знать полезно, хотя бы чтобы не бросаться одну из них решать, встретив на практике. Наверное, иногда полезно еще знать про approximability http://en.wikipedia.org/wiki/Approximation_ratio типичных задач. Но это, наверное, и всё, что может реально пригодиться программисту "в жизни", и то большинство с успехом живет без этого.
Спасибо, напомнило, как дизайнер предложил запилить полуавтоматическую расстановку UI элементов. На что я потратил немало времени, пока понял, что задачка NP. Решил методом "отжига".
Достаточно прочитать классический учебник Джонсона он дает описание почти всех канонических задач, доказательства, полноты там есть много красивых доказательств так что читать интересно чтобы иметь более полный список интересных проблем достаточно просмотреть колонку Джонсона, он отбирал наиболее интересные и важные задачи в течение многих лет
Я прочёл пост и почти всё понял, что невозбранно подняло моё ЧСВ.
> исходная формула имеет удовлетворяющую подстановку тогда и только тогда, когда m-тая смешанная производная этого многочлена (по всем переменным) отлична от нуля. Интересное утверждение. Из чего оно следует? Можете доказать?
И да, за что вы обзываете элементарный дизъюнкт клашем? :)
Кэп идёт на помощь_winnieNovember 12 2010, 23:54:02 UTC
У меня ушло полчаса что бы врубиться. Хотя когда поймёшь, начинает казаться очевидным.
Переходим от такой формы записи A: (a|!b|!c) B: (a|!b|c) C: (!a|!b|!c) D: (!a|!b|c) E: (a|b|c) F: (!a|b)
к такой, где для каждого "атома" x и !x записано, в каком наборе клауз он встречается:
a: A, B, E - набор для a !a: C, D, F - набор для !a b: E, F - набор для b и тд. для !b, c, !c
Теперь что бы понять, дают ли конкретные значения "атомов" (a, !a, b, !b, c, !c) результат формулы 0 или 1 надо объединить все те наборы клауз, которые соответствуют "атомам" равным 1. Если исходная SAT-формула дала 1, значит A=B=C=D=E=F=1, значит объединение наборов по единичным "атомам" дало набор {A,B,C,D,E,F}.
Теперь забываем, что A,B,C,D,E,F были клаузами (конъюнктами), теперь думаем только о том, будет при некотором значении атомов объединение наборов с единичным атомами равно ABCDEF.
(ABE+CDF)(EF+ABCD)(BDE+AC) - это такой способ записать все возможные варианты наборов. Объединение можно записать как умножение, напр. AB*BC это AB2C, на двойку забиваем
( ... )
«Сделать это эффективно (то есть так, чтобы результатом можно было воспользоваться в полиномиальном алгоритме) невозможно, поскольку в итоге получится 2n мономов»
Да пусть висит, чего там. И я на всякий случай объясню всё-таки, а то вдруг кому-то ещё будет непонятно.
Если бы нам пришлось раскрывать скобки, то, действительно, не получилось бы никакой полиномиальной сводимости. Но для оценки производной делать это вовсе не обязательно, в любых вычислениях можно использовать исходную форму многочлена.
Интересно, что то, что ныписал про "Предьявите программу" интуитивно понятно обычным людям (не ученым). Для них (нас) настоящий ученый не тот, кто написал статью про принципы путешествий во времени с высоким индексом цитирования, а тот, кто встроил действующий прототип в Делориан и свалил в прошлое.
О да. Но в данном случае это как раз правильная интуиция, прототип программы-числодробилки, реализующей типичные фантазии вроде http://www.tarusa.ru/~mit/RUS/rus.php, стоит две недели рабочего времени (это еще завышенные оценки) и ноль "ресурсов".
Comments 25
(The comment has been removed)
Reply
Спасибо, напомнило, как дизайнер предложил запилить полуавтоматическую расстановку UI элементов. На что я потратил немало времени, пока понял, что задачка NP. Решил методом "отжига".
Reply
он дает описание почти всех канонических задач, доказательства, полноты
там есть много красивых доказательств так что читать интересно
чтобы иметь более полный список интересных проблем
достаточно просмотреть колонку Джонсона, он отбирал наиболее интересные и важные задачи в течение многих лет
Reply
Reply
Reply
Reply
Выкладывайте, а чо. Я набегу. :)
Reply
> исходная формула имеет удовлетворяющую подстановку тогда и только тогда, когда m-тая смешанная производная этого многочлена (по всем переменным) отлична от нуля.
Интересное утверждение. Из чего оно следует? Можете доказать?
И да, за что вы обзываете элементарный дизъюнкт клашем? :)
Reply
> Каждому возможному набору значений переменных k-SAT формулы соответствует ровно один моном.
> Удовлетворяющим подстановкам соответствуют мономы, содержащие все переменные многочлена
ЧВС тонкая штука да :-\
Reply
Переходим от такой формы записи
A: (a|!b|!c)
B: (a|!b|c)
C: (!a|!b|!c)
D: (!a|!b|c)
E: (a|b|c)
F: (!a|b)
к такой, где для каждого "атома" x и !x записано, в каком наборе клауз он встречается:
a: A, B, E - набор для a
!a: C, D, F - набор для !a
b: E, F - набор для b
и тд. для !b, c, !c
Теперь что бы понять, дают ли конкретные значения "атомов" (a, !a, b, !b, c, !c) результат формулы 0 или 1 надо объединить все те наборы клауз, которые соответствуют "атомам" равным 1. Если исходная SAT-формула дала 1, значит A=B=C=D=E=F=1, значит объединение наборов по единичным "атомам" дало набор {A,B,C,D,E,F}.
Теперь забываем, что A,B,C,D,E,F были клаузами (конъюнктами), теперь думаем только о том, будет при некотором значении атомов объединение наборов с единичным атомами равно ABCDEF.
(ABE+CDF)(EF+ABCD)(BDE+AC) - это такой способ записать все возможные варианты наборов.
Объединение можно записать как умножение, напр. AB*BC это AB2C, на двойку забиваем ( ... )
Reply
Reply
А где тут полиномиальная сводимость?
Reply
Reply
Если бы нам пришлось раскрывать скобки, то, действительно, не получилось бы никакой полиномиальной сводимости. Но для оценки производной делать это вовсе не обязательно, в любых вычислениях можно использовать исходную форму многочлена.
Reply
Reply
Reply
Leave a comment