Решена вторая задача миллениума ?
Решена вторая задача миллениума ?
А если нет?
Последний раз редактировалось Таланов 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
я не видела доказательств, что 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, поэтому это время является не полиномиальным, а псевдополиномиальным.
как оно должно выглядеть?
вот, к примеру, теорема Кука о том, что "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, поэтому это время является не полиномиальным, а псевдополиномиальным.
Последний раз редактировалось Swetlana 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Таланов писал(а):Source of the post
Не-а. Так же как и задачу Пуанкаре и решение её Пелерманом. Наверное я слишком тупой. Просто интересуюсь этим по инерции. Вроде бы говорилось, что решения этих задач должны стимулировать какие-то великие открытия. Пока не заметил даже каких-то хилых движений в этом направлении. Но вы на меня внимания не обращайте, я больше практик нежели теоретик.
Мне тоже больше ближе практика. Просто если мы не понимаем суть, что мы тогда здесь обсуждаем?
Последний раз редактировалось s2009_33 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Таланов, как-то очень перевран Перельман
Последний раз редактировалось Swetlana 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Ну теперь-то вопросов, как полагаю, уже нетs2009_33 писал(а):Source of the post Ну почему же позор. А ник то какой?
Последний раз редактировалось NT 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Таланов не может быть перевранным госпожой Перельман. Она его не знает.
Последний раз редактировалось Таланов 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
На самом деле . Кроме того, шифрование бывает разное. Есть квантовое шифрование, например.12d3 писал(а):Source of the post Скорее закрытия. Если , то шифрование идет лесом.
Мы - это кто? Здесь много людей, которые прекрасно все понимают.s2009_33 писал(а):Source of the post Мне тоже больше ближе практика. Просто если мы не понимаем суть, что мы тогда здесь обсуждаем?
Вообще, возьмите Гэри и Джонсона Вычислительные машины и труднорешаемые задачи и почитайте. Там все несложно (букв только много. Лекциями это проще было осваивать)
Последний раз редактировалось Sonic86 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Мы, ничего. Мужики и бабы, которые в самую суть вникли чего-то обсуждают. А мы пока вникаем.
Последний раз редактировалось Таланов 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Sonic86 писал(а):Source of the postНа самом деле . Кроме того, шифрование бывает разное. Есть квантовое шифрование, например.12d3 писал(а):Source of the post Скорее закрытия. Если , то шифрование идет лесом.Мы - это кто? Здесь много людей, которые прекрасно все понимают.s2009_33 писал(а):Source of the post Мне тоже больше ближе практика. Просто если мы не понимаем суть, что мы тогда здесь обсуждаем?
Вообще, возьмите Гэри и Джонсона Вычислительные машины и труднорешаемые задачи и почитайте. Там все несложно (букв только много. Лекциями это проще было осваивать)
Я про себя и Таланова говорил. Если понимаете и у вас есть время, может быть сделаете краткое сообщение?
Наверное реально объяснить это на общеупотребимом языке, хотя возможно это не просто.
Последний раз редактировалось s2009_33 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Проблему Кука? Огласите весь список, пожалуйста!
Последний раз редактировалось Таланов 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 66 гостей