Решена вторая задача миллениума ?

Рубен · Сообщение **Рубен** » 30 ноя 2012, 22:39

peregoudov писал(а):Source of the post По крайней мере из всей книги мне этот раздел понравился, в отличие от других, по физике. Может оттого, что я в этом профан...

Наверное потому, что Пенроуз -- математик, а не физик.

Sonic86 · Сообщение **Sonic86** » 01 дек 2012, 06:43

Swetlana писал(а):Source of the post Предлагаю модераторам компутер сайенс сделать тему с названием
"Что вы всегда хотели узнать о ~~сексе~~ о NP-полноте, но боялись спросить", не всё же об антивирусниках писать

Вообще, какбе ~~секс~~ NP-полнота - это матан в чистом виде, а не CS.

Swetlana писал(а):Source of the post 3. мои собственные знания крайне ограничены и устарели, вместе с книгой Гэри-Джонсона

Сам Гэри-Джонсон неужели устарел?! Не, там же теоремы...

Swetlana писал(а):Source of the post Эти алгоритмы нетрудно выучить

Ну это уже юмор Для проверки числа на простоту найден полиномиальный алгоритм, но его еще никто не запрограммировал.

Попробую и я кратко (но я не лектор, получится сумбурно). Предполагаю, что всем понятно, что такое машина Тьюринга (далее МТ).
Рассматриваются массовые задачи и алгоритмы их решения. Массовая задача - это множество однородных задач, параметризованных каким-то параметром $$n$$

. Алгоритм ее решения - МТ, у которой в начальном состоянии на ленте записаны входные данные любого экземпляра массовой задачи. МТ читает их и выдает ответ за некоторое число шагов $$t_n$$

. Если существует многочлен $P(n): t_n\leqslant P(n)$ (т.е. если время решения задачи полиномиально - ограничено сверху многочленом от $$n$$

), то говорят, что задача принадлежит классу $$P$$

. Далее вводятся в рассмотрение недетерминированные машины Тьюринга НДМТ. НДМТ - это МТ с некоторым устройством (оракул?), устройство сначала пишет, не читая входные данные, на ленте ответ, а МТ его проверяет за полиномиальное время. Если задача может быть решена НДМТ, то говорят, что она принадлежит классу $$NP$$

. Грубо говоря, $$NP$$

-задачи, это те, у которых ответ проверяется за полиномиальное время.
Ясно, что $P\subset NP$ , поскольку МТ, решающая задачу за полиномиальное время, выпишет и ее ответ не дольше чем за полиномиальное время.
Далее, используется идея универсальности: все $$NP$$

-задачи сводят к одной задаче ВЫПОЛНИМОСТЬ (или 3-ВЫПОЛНИМОСТЬ - не помню) (по-аглицки - SAT или $$k-SAT$$

, именно ее и пытался решить индийский математик). Задача ВЫПОЛНИМОСТЬ следующая: дана конъюнктивная нормальная форма КНФ от $$n$$

переменных длинной не более чем полином от $$n$$

, нужно определить ее решение (пример: $(x_1\vee x_2\vee x_4)\wedge (x_2\veex_3\vee\neg x_4)\wedge \neg x_1=1$ ). Ясно, что задача ВЫПОЛНИМОСТЬ является $$NP$$

-задачей: оракул пишет решение за $$O(n)$$

шагов, а проверка происходит за $$O(L(n))$$

шагов, где $$L$$

- длина КНФ. Сведение всех $$NP$$

-задач к задаче ВЫПОЛНИМОСТЬ - это теорема Кука на 5 страниц, но суть ее очень проста: действие МТ (следует вспомнить, что МТ - это лента длиной не более многочлена от $$n$$

, конечный алфавит $$A$$

, конечное число состояний $$Q$$

и конечное число правил преобразований вида $a_iq_j\to a_kq_m T$ ) кодируется множеством высказываний, конъюнкция которых и составит КНФ (довольно длинную, но полиномиальной длины). В доказательстве приводится явное кодирование всех деталей работы МТ, мы ограничимся примерами (пишу по памяти, могу наврать): $$t$$

- момент времени работы НДМТ ( $$t=0,1,...,Q(n)$$

), $X_{t,k,a}=1\Leftrightarrow$ в ячейке ленты с номером $$k$$

(поскольку задача - $$NP$$

, то длина ленты не более полиномиальной длины) в момент времени $$t$$

находится символ $$a$$

. Число переменных $X_{t,k,a}$ не превосходит полинома от $$n$$

, потому мы можем закодировать состояние ленты во все моменты времени работы НДМТ. Далее также кодируются состояния МТ (булевы переменные типа "в момент $$t$$

НДМТ находится в состоянии $$q$$

"), правила работы НДМТ в виде импликаций, которые переписываются в виде множества дизъюнкций, входные данные (уже закодировали) и итоговый ответ тоже. В итоге, мы любую $$NP$$

-задачу конструктивным образом свели к задаче ВЫПОЛНИМОСТЬ.
Задача, к которой м.б. сведена любая задача называется $$NP$$

-полной задачей. Теорема Кука нам показывает, что $$NP$$

-полная задача существует - это задача ВЫПОЛНИМОСТЬ. Далее, товарищи ученые собирают чисто эмпирически множество разных задач и показывают, что они относятся к классу $$NP$$

. Простой эквивалентностью устанавливается подкласс $$NP$$

-задач - это $$NP$$

-полные задачи - это класс эквивалентности задач, эквивалентных задаче ВЫПОЛНИМОСТЬ. $$NP$$

-полных задач чуть менее чем дофига и они очень просты: решение системы булевых линейных ограничений, поиск клики, максимального независимого множества на графе, поиск вершинных и реберных покрытий, поиск паросочетаний, задача коммивояжера и т.п. Эквивалентность доказывается явным способом. Например, задача ВЫПОЛНИМОСТЬ может быть сведена к задаче булева линейного программирования (ЦЛП) так: множеству переменных $$x_j$$

одной задачи биективно ставится в соответствие множество переменных задачи БЛП $$y_j$$

( $x_j\leftrightarrow y_j$ ), большой конъюнкции ставится в соответствие система, а элементарным дизъюнкциям $x_{a_1}\vee...\vee x_{a_k}\leftrightarrow y_{a_1}+...+y_{a_k}\geqslant 1$ . Получается, что мы одну и ту же по сложности задачу можем преобразовывать в очень разные задачи. Например, БЛП от ВЫПОЛНИМОСТИ отличается сильно: ЦЛП можно сводить к задачам ЛП и решать методом Гомори - изоморфный алгоритм для задачи ВЫПОЛНИМОСТЬ, мягко говоря, неочевиден. По мере сведения $$NP$$

-полных задач друг к другу товарищи ученые есс-но пытались решить хотя бы одну из них. Но эквивалентность держиться: ни для одной $$NP$$

-полной задачи полиномиальный алгоритм решения не придуман. Данный факт какбе намекает нам, что это неспроста. Отсюда и появилась гипотеза $$P?=NP$$

(которая, ИМХО, решается отрицательно, либо неразрешима вообще).
Заметим также, что есть еще логическая формулировка проблемы, я ее не знаю. Есть также множество задач (например, факторизация и, кажется, изоморфизм графов), которые неизвестно - $$NP$$

-полные они или все-таки относятся к $$P$$

. Есть множество $$NP$$

-задач, для которых $$NP$$

-полнота не доказана. Есть еще какой-то класс $$coNP$$

и

, но я про них не знаю ничего.
Читайте книжки, короче.

Swetlana · Сообщение **Swetlana** » 01 дек 2012, 07:37

Sonic86 писал(а):Source of the post
"Что вы всегда хотели узнать о сексе и о NP-полноте, но боялись спросить",
Вообще, какбе секс в его NP-полноте - это матан в чистом виде, а не CS.

так, а мужики-то не знают
срочно заводите тему, где хотите :rolleyes:

Сам Гэри-Джонсон неужели устарел?!

четырехтомник (!) давно уже вышел, переводить его никто не собирается и английский скан никто не выложил
была поучительная история, Павловский не даст соврать,
не могла доказать NP-полноту одной задачи, потом плюнула, написала письмо профессору Пападимитриу, заодно поздравила с православным рождеством
на следующий день получила доказательство в 3 строчки

В ответ на мой вопрос профессор Пападимитриу любезно сообщил следующее.
1. Для решетчатых графов, представляющих собой прямоугольную решетку, где все вершины находятся на расстоянии=1 доказана NP-полнота существования гам. цикла.
2. Полиномиальная сводимость заключается в следующем: вершины исходного графа вкладываются в 45-градусную решетку на плоскости.

если бы я знала, что гам. цикл NP-полный и для решотчатых графов, наверно, сама бы сообразила

Ну это уже юмор

вчера на лекции так и сказала: "все эти алгоритмы давно известны, весь второй курс вы их будете учить и сдавать, я вас предупредила :ph34r: "

Задачу линейного программирования долго подозревали в NP-полноте, пока Хачиян не нашёл полиномиальный алгоритм, только толку от него, неэффективный, так что с точки зрения приложений можно смело считать что P<>NP.

Sonic86 · Сообщение **Sonic86** » 01 дек 2012, 07:47

Swetlana писал(а):Source of the post так, а мужики-то не знают
срочно заводите тему, где хотите :rolleyes:

Неохота мне. Тем более, что мой текст достаточно кривой. А вообще - книжки лучше читать для ликбеза
Может A.I. просто перетащит тему, куда ему вздумается, да и все. В целом тут флейма почти нет.

Swetlana писал(а):Source of the post
Сам Гэри-Джонсон неужели устарел?!
четырехтомник (!) давно уже вышел, переводить его никто не собирается и английский скан никто не выложил

Как 4-хтомник!?

У меня обычная книжка, и то там полкнижки - это сами задачи и ссылки на док-во их NP-полноты.

Swetlana писал(а):Source of the post Задачу линейного программирования долго подозревали в NP-полноте, пока Хачиян не нашёл полиномиальный алгоритм, только толку от него, неэффективный, так что с точки зрения приложений можно смело считать что P<>NP.

Опа! А я и не знал! Спасибо!

Swetlana писал(а):Source of the post "Что вы всегда хотели узнать о сексе и о NP-полноте, но боялись спросить",
Sonic86 писал(а):Source of the post Вообще, какбе секс в его NP-полноте - это матан в чистом виде, а не CS.

:lool: теги зачеркивания не скопировались. Не знал, что секс - это NP-полная задача :lool: .

Swetlana · Сообщение **Swetlana** » 01 дек 2012, 08:42

coNP - задачи, дополнительные к NP, не решаются НДМТ за полиномиальное время, пересекаются с NP по P.
Разумеется, что они не решаются НДМТ за полиномиальное время не доказано
хотя хз, я ведь не знаю, что в новом 4-томнике Гэри-Джонсона написано

Тему тащить никуда не надо, в следующем семестре у меня будет небольшая нагрузка, не 26 часов в неделю, как сейчас... если бесцельно не шататься по 4 форумам, то можно свои лекции под tex переделать
Гэри-Джонсон сложен для понимания прикладника, его надо адаптировать, кто знает больше, тот поправит и дополнит

тема будет называться "Что вы всегда хотели узнать о сексуальной NP-полноте, но боялись спросить"

Рубен · Сообщение **Рубен** » 01 дек 2012, 09:38

Sonic86 писал(а):Source of the post Вообще, какбе ~~секс~~ NP-полнота - это матан в чистом виде, а не CS.

Не, без Counter Strike тут не обошлось :no:

folk · Сообщение **folk** » 01 дек 2012, 14:11

А было упоминания что NP полные - это класс задач решаемый за полиномиальное время недетерминированной машиной Тьюринга? По моему это интуитивно наиболее простое описание класса NP.

A.I. · Сообщение **A.I.** » 01 дек 2012, 14:19

Рубен писал(а):Source of the post Не, без Counter Strike тут не обошлось

а я говорю q3dm11! А может даже q2dm1 the Edge

Sonic86 писал(а):Source of the post Может A.I. просто перетащит тему, куда ему вздумается, да и все.

куда хотите?

Sonic86 · Сообщение **Sonic86** » 01 дек 2012, 15:45

A.I. писал(а):Source of the post куда хотите?

Раздела с дискреткой у нас нет. Ну значит в Computer Science, либо в Прочие разделы математики.

A.I. · Сообщение **A.I.** » 01 дек 2012, 15:52

конкретизируйте конечную точку перемещения

yourdomain.com