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

Таланов

А если нет?

Swetlana · Сообщение **Swetlana** » 30 ноя 2012, 14:33

я не видела доказательств, что P<>NP
как оно должно выглядеть?

вот, к примеру, теорема Кука о том, что "3-выполнимость" NP-полная задача.
Вначале легко показать, что эта задача лежит в NP, то есть решается НДМТ (недетерминированной машиной Тьюринга) за полиномиальное время
А потом нелегко показать, что эта задача "самая трудная" в NP - любую другую задачу из NP можно свести к "3-выполнимости" за полиномиальное время.
То есть все NP-полные между собой эквивалентны, все они "самые трудные" в NP. Решить одну из них за полиномиальное время - решить все, которые к ней полиномиально сводятся, за полиномиальное время.
Поскольку они все друг к другу сводятся, то P=NP.

Чтобы доказать, что P<>NP нужно для одной задачи из NP доказать, что её нельзя решить ДМТ (детерминированной машиной Тьюринга) за полиномиальное время. То есть ни одна ДМТ при "разумных" схемах кодирования входного слова эту задачу за полиномиальное время не решит.
Понятия не имею, как это доказывать

Что касается задачи из википедии, то это какое-то извращение модельной задачи
"Сумма размеров", Гэри, Джонсон, "Вычислительные машины и труднорешаемые задачи", стр. 283

Условие. Заданы n-элементное множество A, каждый элемент имеет целый положительный вес (или размер) и целое положительное число B.
Вопрос. Можно ли набрать заданный вес (размер) B с помощью элементов множества A? т.е. существует ли выборка из A такая, что сумма размеров (весов) его элементов равна B?

Эта задача даже не NP-полная в сильном смысле, она прекрасно решается динамическим программированием за время O(nB). Фишка в том, что B может быть очень большим, экспоненциальным от n, поэтому это время является не полиномиальным, а псевдополиномиальным.

s2009_33 · Сообщение **s2009_33** » 30 ноя 2012, 14:35

Таланов писал(а):Source of the post
s2009_33 писал(а):Source of the post
А вы понимаете суть данной теоремы?

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

Мне тоже больше ближе практика. Просто если мы не понимаем суть, что мы тогда здесь обсуждаем?

Swetlana · Сообщение **Swetlana** » 30 ноя 2012, 14:39

Таланов, как-то очень перевран Перельман

NT · Сообщение NT » 30 ноя 2012, 14:48

s2009_33 писал(а):Source of the post Ну почему же позор. А ник то какой?

Ну теперь-то вопросов, как полагаю, уже нет

Таланов

Swetlana писал(а):Source of the post
Таланов, как-то очень перевран Перельман

Таланов не может быть перевранным госпожой Перельман. Она его не знает.

Sonic86 · Сообщение **Sonic86** » 30 ноя 2012, 14:50

12d3 писал(а):Source of the post Скорее закрытия. Если , то шифрование идет лесом.

На самом деле $P\neq NP$ . Кроме того, шифрование бывает разное. Есть квантовое шифрование, например.

s2009_33 писал(а):Source of the post Мне тоже больше ближе практика. Просто если мы не понимаем суть, что мы тогда здесь обсуждаем?

Мы - это кто? Здесь много людей, которые прекрасно все понимают.
Вообще, возьмите Гэри и Джонсона Вычислительные машины и труднорешаемые задачи и почитайте. Там все несложно (букв только много. Лекциями это проще было осваивать)

Таланов

s2009_33 писал(а):Source of the post
Просто если мы не понимаем суть, что мы тогда здесь обсуждаем?

Мы, ничего. Мужики и бабы, которые в самую суть вникли чего-то обсуждают. А мы пока вникаем.

s2009_33 · Сообщение **s2009_33** » 30 ноя 2012, 15:04

Sonic86 писал(а):Source of the post
12d3 писал(а):Source of the post Скорее закрытия. Если , то шифрование идет лесом.
На самом деле $P\neq NP$ . Кроме того, шифрование бывает разное. Есть квантовое шифрование, например.

s2009_33 писал(а):Source of the post Мне тоже больше ближе практика. Просто если мы не понимаем суть, что мы тогда здесь обсуждаем?
Мы - это кто? Здесь много людей, которые прекрасно все понимают.
Вообще, возьмите Гэри и Джонсона Вычислительные машины и труднорешаемые задачи и почитайте. Там все несложно (букв только много. Лекциями это проще было осваивать)

Я про себя и Таланова говорил. Если понимаете и у вас есть время, может быть сделаете краткое сообщение?
Наверное реально объяснить это на общеупотребимом языке, хотя возможно это не просто.

Таланов

Sonic86 писал(а):Source of the post
Здесь много людей, которые прекрасно все понимают.

Проблему Кука? Огласите весь список, пожалуйста!

yourdomain.com