Наверное потому, что Пенроуз -- математик, а не физик.peregoudov писал(а):Source of the post По крайней мере из всей книги мне этот раздел понравился, в отличие от других, по физике. Может оттого, что я в этом профан...
Решена вторая задача миллениума ?
Решена вторая задача миллениума ?
Последний раз редактировалось Рубен 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Вообще, какбеSwetlana писал(а):Source of the post Предлагаю модераторам компутер сайенс сделать тему с названием
"Что вы всегда хотели узнать осексео NP-полноте, но боялись спросить", не всё же об антивирусниках писать
Сам Гэри-Джонсон неужели устарел?! Не, там же теоремы...Swetlana писал(а):Source of the post 3. мои собственные знания крайне ограничены и устарели, вместе с книгой Гэри-Джонсона
Ну это уже юмор Для проверки числа на простоту найден полиномиальный алгоритм, но его еще никто не запрограммировал.Swetlana писал(а):Source of the post Эти алгоритмы нетрудно выучить
Попробую и я кратко (но я не лектор, получится сумбурно). Предполагаю, что всем понятно, что такое машина Тьюринга (далее МТ).
Рассматриваются массовые задачи и алгоритмы их решения. Массовая задача - это множество однородных задач, параметризованных каким-то параметром
Ясно, что
Далее, используется идея универсальности: все
Задача, к которой м.б. сведена любая задача называется
Заметим также, что есть еще логическая формулировка проблемы, я ее не знаю. Есть также множество задач (например, факторизация и, кажется, изоморфизм графов), которые неизвестно -
Читайте книжки, короче.
Последний раз редактировалось Sonic86 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Sonic86 писал(а):Source of the post
"Что вы всегда хотели узнать о сексе и о NP-полноте, но боялись спросить",
Вообще, какбе секс в его NP-полноте - это матан в чистом виде, а не CS.
так, а мужики-то не знают
срочно заводите тему, где хотите :rolleyes:
Сам Гэри-Джонсон неужели устарел?!
четырехтомник (!) давно уже вышел, переводить его никто не собирается и английский скан никто не выложил
была поучительная история, Павловский не даст соврать,
не могла доказать NP-полноту одной задачи, потом плюнула, написала письмо профессору Пападимитриу, заодно поздравила с православным рождеством
на следующий день получила доказательство в 3 строчки
В ответ на мой вопрос профессор Пападимитриу любезно сообщил следующее.
1. Для решетчатых графов, представляющих собой прямоугольную решетку, где все вершины находятся на расстоянии=1 доказана NP-полнота существования гам. цикла.
2. Полиномиальная сводимость заключается в следующем: вершины исходного графа вкладываются в 45-градусную решетку на плоскости.
если бы я знала, что гам. цикл NP-полный и для решотчатых графов, наверно, сама бы сообразила
Ну это уже юмор
вчера на лекции так и сказала: "все эти алгоритмы давно известны, весь второй курс вы их будете учить и сдавать, я вас предупредила :ph34r: "
Задачу линейного программирования долго подозревали в NP-полноте, пока Хачиян не нашёл полиномиальный алгоритм, только толку от него, неэффективный, так что с точки зрения приложений можно смело считать что P<>NP.
Последний раз редактировалось Swetlana 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Неохота мне. Тем более, что мой текст достаточно кривой. А вообще - книжки лучше читать для ликбезаSwetlana писал(а):Source of the post так, а мужики-то не знают
срочно заводите тему, где хотите :rolleyes:
Может A.I. просто перетащит тему, куда ему вздумается, да и все. В целом тут флейма почти нет.
Как 4-хтомник!?Swetlana писал(а):Source of the postчетырехтомник (!) давно уже вышел, переводить его никто не собирается и английский скан никто не выложилСам Гэри-Джонсон неужели устарел?!
![Удивлен :o](./images/smilies/icon_e_surprised.gif)
Опа! А я и не знал! Спасибо!Swetlana писал(а):Source of the post Задачу линейного программирования долго подозревали в NP-полноте, пока Хачиян не нашёл полиномиальный алгоритм, только толку от него, неэффективный, так что с точки зрения приложений можно смело считать что P<>NP.
:lool: теги зачеркивания не скопировались. Не знал, что секс - это NP-полная задача :lool: .Swetlana писал(а):Source of the post "Что вы всегда хотели узнать о сексе и о NP-полноте, но боялись спросить",Sonic86 писал(а):Source of the post Вообще, какбе секс в его NP-полноте - это матан в чистом виде, а не CS.
Последний раз редактировалось Sonic86 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
coNP - задачи, дополнительные к NP, не решаются НДМТ за полиномиальное время, пересекаются с NP по P.
Разумеется, что они не решаются НДМТ за полиномиальное время не доказано
хотя хз, я ведь не знаю, что в новом 4-томнике Гэри-Джонсона написано
Тему тащить никуда не надо, в следующем семестре у меня будет небольшая нагрузка, не 26 часов в неделю, как сейчас... если бесцельно не шататься по 4 форумам, то можно свои лекции под tex переделать
Гэри-Джонсон сложен для понимания прикладника, его надо адаптировать, кто знает больше, тот поправит и дополнит
тема будет называться "Что вы всегда хотели узнать о сексуальной NP-полноте, но боялись спросить"
Разумеется, что они не решаются НДМТ за полиномиальное время не доказано
хотя хз, я ведь не знаю, что в новом 4-томнике Гэри-Джонсона написано
Тему тащить никуда не надо, в следующем семестре у меня будет небольшая нагрузка, не 26 часов в неделю, как сейчас... если бесцельно не шататься по 4 форумам, то можно свои лекции под tex переделать
Гэри-Джонсон сложен для понимания прикладника, его надо адаптировать, кто знает больше, тот поправит и дополнит
тема будет называться "Что вы всегда хотели узнать о сексуальной NP-полноте, но боялись спросить"
Последний раз редактировалось Swetlana 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Не, без Counter Strike тут не обошлось :no:Sonic86 писал(а):Source of the post Вообще, какбесексNP-полнота - это матан в чистом виде, а не CS.
Последний раз редактировалось Рубен 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
А было упоминания что NP полные - это класс задач решаемый за полиномиальное время недетерминированной машиной Тьюринга? По моему это интуитивно наиболее простое описание класса NP.
Последний раз редактировалось folk 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Рубен писал(а):Source of the post Не, без Counter Strike тут не обошлось
а я говорю q3dm11! А может даже q2dm1 the Edge
Sonic86 писал(а):Source of the post Может A.I. просто перетащит тему, куда ему вздумается, да и все.
куда хотите?
Последний раз редактировалось A.I. 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
Раздела с дискреткой у нас нет. Ну значит в Computer Science, либо в Прочие разделы математики.A.I. писал(а):Source of the post куда хотите?
Последний раз редактировалось Sonic86 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Решена вторая задача миллениума ?
конкретизируйте конечную точку перемещения
Последний раз редактировалось A.I. 28 ноя 2019, 15:14, всего редактировалось 1 раз.
Причина: test
Причина: test
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 5 гостей