Почему P-NP проблема такая сложная

Nov 13, 2010 00:12

(научно-непопулярный пост ( Read more... )

math

Leave a comment

Comments 25

(The comment has been removed)

plakhov November 13 2010, 07:55:01 UTC
Список типичных NP-сложных задач, что именно обычно делает задачу NP-сложной, и что это на самом деле означает, пожалуй, знать полезно, хотя бы чтобы не бросаться одну из них решать, встретив на практике. Наверное, иногда полезно еще знать про approximability http://en.wikipedia.org/wiki/Approximation_ratio типичных задач. Но это, наверное, и всё, что может реально пригодиться программисту "в жизни", и то большинство с успехом живет без этого.

Reply

dryndoragis April 28 2023, 09:50:49 UTC

Спасибо, напомнило, как дизайнер предложил запилить полуавтоматическую расстановку UI элементов. На что я потратил немало времени, пока понял, что задачка NP. Решил методом "отжига".

Reply

illy_drinker November 16 2010, 04:48:26 UTC
Достаточно прочитать классический учебник Джонсона
он дает описание почти всех канонических задач, доказательства, полноты
там есть много красивых доказательств так что читать интересно
чтобы иметь более полный список интересных проблем
достаточно просмотреть колонку Джонсона, он отбирал наиболее интересные и важные задачи в течение многих лет

Reply


netmaxed November 12 2010, 21:27:53 UTC
вот мне тоже надо в жж свои рабочие идеи начать выкладывать, тогда оставшийся народ точно разбежится :)

Reply

plakhov November 13 2010, 08:49:07 UTC
а в какой области?

Reply

netmaxed November 13 2010, 17:06:49 UTC
структура и свойства мембранных протеинов :)

Reply

plakhov November 13 2010, 17:28:38 UTC
Клаааасс
Выкладывайте, а чо. Я набегу. :)

Reply


anonymous November 12 2010, 21:58:41 UTC
Я прочёл пост и почти всё понял, что невозбранно подняло моё ЧСВ.

> исходная формула имеет удовлетворяющую подстановку тогда и только тогда, когда m-тая смешанная производная этого многочлена (по всем переменным) отлична от нуля.
Интересное утверждение. Из чего оно следует? Можете доказать?

И да, за что вы обзываете элементарный дизъюнкт клашем? :)

Reply

anonymous November 12 2010, 23:25:16 UTC
> Интересное утверждение. Из чего оно следует?

> Каждому возможному набору значений переменных k-SAT формулы соответствует ровно один моном.
> Удовлетворяющим подстановкам соответствуют мономы, содержащие все переменные многочлена

ЧВС тонкая штука да :-\

Reply

Кэп идёт на помощь _winnie November 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, на двойку забиваем ( ... )

Reply

Re: Кэп идёт на помощь anonymous November 13 2010, 07:01:09 UTC
Спасибо, Кэп, ты опять спас мир :)

Reply


anonymous November 12 2010, 23:07:52 UTC
«Сделать это эффективно (то есть так, чтобы результатом можно было воспользоваться в полиномиальном алгоритме) невозможно, поскольку в итоге получится 2n мономов»

А где тут полиномиальная сводимость?

Reply

anonymous November 12 2010, 23:10:06 UTC
ОК, прошу удалить коммент, сразу не понял.

Reply

plakhov November 13 2010, 08:03:02 UTC
Да пусть висит, чего там. И я на всякий случай объясню всё-таки, а то вдруг кому-то ещё будет непонятно.

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

Reply


musasy November 13 2010, 12:08:18 UTC
Интересно, что то, что ныписал про "Предьявите программу" интуитивно понятно обычным людям (не ученым). Для них (нас) настоящий ученый не тот, кто написал статью про принципы путешествий во времени с высоким индексом цитирования, а тот, кто встроил действующий прототип в Делориан и свалил в прошлое.

Reply

plakhov November 13 2010, 12:14:41 UTC
О да. Но в данном случае это как раз правильная интуиция, прототип программы-числодробилки, реализующей типичные фантазии вроде http://www.tarusa.ru/~mit/RUS/rus.php, стоит две недели рабочего времени (это еще завышенные оценки) и ноль "ресурсов".

Reply


Leave a comment

Up