Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 127
Вы бы хоть ссылку дали, о чем речь.
Спасибо, добавил.
А вы не могли бы еще гденибудь в топике или в заголовке упомянуть, что речь о «классе сложности задачи», а не о числе P и о нем же помноженном на N.
По-моему это очевидно, особенно в блоге «Алгоритмы».
хех, да и слава богу =)
представляете жизнь в мире, где всех беспокоит проблема NP-полноты и равенства P=NP =)
хотя что-то подобное АБС в книге «Полдень, XXII век» описали, но все равно кесарю кесарево.
представляете жизнь в мире, где всех беспокоит проблема NP-полноты и равенства P=NP =)
хотя что-то подобное АБС в книге «Полдень, XXII век» описали, но все равно кесарю кесарево.
Нда… горячая новость (не факт, что правда) про прикольную прогу для айфона — -216 голосов, а горячая новость (не факт, что правда) про фундаментальную проблему современной Computer Science — 19 голосов. Ништяк! Какая просвещенная аудитория-то ):)))
Тогда это будет самой высокой оценкой за топик, какую я видел на Хабре.
+1154 — самая высокая что видел на хабре
habrahabr.ru/blogs/infosecurity/70330/
habrahabr.ru/blogs/infosecurity/70330/
просто народ который читает ветку больше забивает на всякие там плюсы и минусы. Важно содержание статьи, а не кнопочки какие-то.
Имхо, качество топика определяется по количеству пользователей, добавивших пост в избранное.
К чему излишний снобизм и сокрытие смысла? N и P — это такие буквы английского алфавита, ими можно много что обозначить и они далеко не у всех ассоциируются со сложностью алгоритмов. Если просто написать 2 слова, топик станет понятен еще N% людей.
надеюсь, что так лучше.
ссылка на вики должна все прояснить.
ссылка на вики должна все прояснить.
У большинства посещающих Хабр эти символы стойко ассоциируются (а у кого-то еще и с нахлынувшими воспоминаниями об университетских годах) с теорией сложности вычислений.
А те у кого не возникает в душе радости, что эта загадка века наконец возможно решена, просто пройдут мимо. Мне например совсем не интересны статьи про Эппл — я их не открываю, и мне совершенно безразлично, что значат те или иные термины или сокращения в них.
А те у кого не возникает в душе радости, что эта загадка века наконец возможно решена, просто пройдут мимо. Мне например совсем не интересны статьи про Эппл — я их не открываю, и мне совершенно безразлично, что значат те или иные термины или сокращения в них.
У меня эти буквы ассоциируются с полупроводниками
(я IT-шник по совместительству, основное образование у меня по «железной» части)
(я IT-шник по совместительству, основное образование у меня по «железной» части)
Вы ошибаетесь. Буквы N и P могут означать только класс сложности задачи.
Хотел бы я чтоб это было так, и в жизни всё было бы так просто и однозначно… Увы боюсь это не так.
Правда?
Хотя в контексте алгоритмов по всей видимости Вы правы.
Хотя в контексте алгоритмов по всей видимости Вы правы.
А вот пост в котором популярно объяснялось что такое P и NP.
Доказательство в PDF. В нём применяется статистическая физика, что несколько необычно. По всей видимости, автор потратил несколько лет на этот труд.
За доказательство назначен приз в $1,000,000, но об этом ниже. Поясню суть проблемы.
Класс сложности P (или nO(1)) — это множество алгоритмов, время работы которых не сильно зависит от объёма входных данных. Это быстрые алгоритмы. Точнее: которые могут быть решены на детерминированной машине Тьюринга за полиноминальное время (многочлен от размера данных).
Класс сложности NP — это множество алгоритмов решений, ответ «да» на которые можно проверить за полиноминальное время. NP-полный класс сложности — подмножество NP алгоритмов, для которых неизвестно быстрое решение (за полиноминальное время).
Пример NP-полного алгоритма решения: задача коммивояжёра — проложить оптимальный путь через заданные города, посещая их только один раз. Проверить решение можно быстро (класс P), а найти решение быстро нельзя (класс NP-полный).
Изобразить отношение классов в случае обоих решений теоремы можно на диаграмме Эйлера-Венна:
Доказательство P ≠ NP не только решит одну из семи задач тысячелетия (математический институт Clay, 6 из 7 ещё не решено, решена гипотеза Пуанкаре), но и покажет, что множество криптографических алгоритмов (в частности, на основе проблемы факторизации: публичные и приватные ключи) в безопасности. Также раздел теории вычислений получит полезные инструменты для доказательства других теорем, и не будет биться за поиск P-решений, а сосредоточится на прочих проблемах.
За доказательство назначен приз в $1,000,000, но об этом ниже. Поясню суть проблемы.
Класс сложности P (или nO(1)) — это множество алгоритмов, время работы которых не сильно зависит от объёма входных данных. Это быстрые алгоритмы. Точнее: которые могут быть решены на детерминированной машине Тьюринга за полиноминальное время (многочлен от размера данных).
Класс сложности NP — это множество алгоритмов решений, ответ «да» на которые можно проверить за полиноминальное время. NP-полный класс сложности — подмножество NP алгоритмов, для которых неизвестно быстрое решение (за полиноминальное время).
Пример NP-полного алгоритма решения: задача коммивояжёра — проложить оптимальный путь через заданные города, посещая их только один раз. Проверить решение можно быстро (класс P), а найти решение быстро нельзя (класс NP-полный).
Изобразить отношение классов в случае обоих решений теоремы можно на диаграмме Эйлера-Венна:
Доказательство P ≠ NP не только решит одну из семи задач тысячелетия (математический институт Clay, 6 из 7 ещё не решено, решена гипотеза Пуанкаре), но и покажет, что множество криптографических алгоритмов (в частности, на основе проблемы факторизации: публичные и приватные ключи) в безопасности. Также раздел теории вычислений получит полезные инструменты для доказательства других теорем, и не будет биться за поиск P-решений, а сосредоточится на прочих проблемах.
да, многие специалисты в области криптографии наконец вздохнут спокойно и выпьют за здравие Винайя =)
P.S. вообще, очень многое поставлено на кон для этого ученого. Не хотел бы я в данный_промежуток_времени оказаться на его месте.
P.S. вообще, очень многое поставлено на кон для этого ученого. Не хотел бы я в данный_промежуток_времени оказаться на его месте.
Выше я привёл ссылку на 63-х страничное доказательство, вот 98-и страничное доказательство. Содержимое одинаковое, но разный шрифт, возможно, кому-то пригодится для ссылок.
Как написал автор, “I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.” — «Я рад представить доказательство, что P не равно NP, которое прикладываю в шрифтах размером 10pt и 12pt.» Думаю, это решающий фактор.
Как написал автор, “I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.” — «Я рад представить доказательство, что P не равно NP, которое прикладываю в шрифтах размером 10pt и 12pt.» Думаю, это решающий фактор.
Факторизация (как и все остальные трудные задачи используемые в криптографии) не является NP-полной, так что доказательство P!=NP никак не поможет криптографам.
Вы правы, криптография целиком на это не полагается, поскольку NP-полный — это о худшем случае, т.е. «существует сообщение, которое сложно расшифровать».
Некоторые криптографические алгоритмы опираются на проблему 3SAT, которая NP-полная. Задачи дискретного логарифмирования и факторизации считаются NP (факторизация ещё и co-NP) — но вне P и вне NP-полных, поэтому доказательство P ≠ NP для них играет роль.
Некоторые криптографические алгоритмы опираются на проблему 3SAT, которая NP-полная. Задачи дискретного логарифмирования и факторизации считаются NP (факторизация ещё и co-NP) — но вне P и вне NP-полных, поэтому доказательство P ≠ NP для них играет роль.
Не совсем правда.
NP-полная задача — это задача, к которой любая другая NP-задача сводится за полиномиальное время.
NP-полная задача — это задача, к которой любая другая NP-задача сводится за полиномиальное время.
Верно, я просто сформулировал доступнее, менее формально.
Вы написали, что NP-полные задачи — это задачи, для которых неизвестно быстрое решение.
Это неправда.
Во-первых, существуют задачи, для которых быстрое решение не существует, но NP-полнота которых не доказана.
Во-вторых, быстрое решение может быть сегодня неизвестно, а завтра его обнаружат. Что же, задача перестанет быть NP-полной?
В-третьих, если бы оказалось, что P=NP, то класс NP-complete прекратил бы свое существование?
Это неправда.
Во-первых, существуют задачи, для которых быстрое решение не существует, но NP-полнота которых не доказана.
Во-вторых, быстрое решение может быть сегодня неизвестно, а завтра его обнаружат. Что же, задача перестанет быть NP-полной?
В-третьих, если бы оказалось, что P=NP, то класс NP-complete прекратил бы свое существование?
В-третьих, если бы оказалось, что P=NP, то класс NP-complete прекратил бы свое существование?Нет, но P, NP и NP-complete стали бы равны. Вроде, логично?
Если завтра обнаружат быстрое решение NP-полной задачи, то любая NP задача сможет быть решена быстро. Пока этого не произошло, я и привёл упрощённую формулировку.
Ниже спрашивают, какое ещё практическое значение имеет это доказательство. Я постараюсь объяснить.
Существует класс coNP — класс P входит и в NP, и в coNP. Если доказано, что NP ≠ coNP, то в coNP не может быть NP-полных проблем.
Приведу некоторые не искусственные проблемы, которые не попадают в класс P и NP-полный:
1. Факторизация целых чисел. Дано целое число, найти простые сомножители.
2. Кратчайший вектор в решётке. Дана решётка L в Rⁿ и целое k, будет ли длина (Евклидова) кратчайшего вектора L находиться в диапазоне [k; kn]?
3. Стохастические игры. Чёрные, Белые и Природа по очереди перемещают фишку по вершинам направленного графа. Природа перемещает случайно. Дан граф, начальная и конечная вершина для фишки. Есть ли у Белых стратегия, которая гарантирует, что фишка достигнет цели с вероятностью ≥ ½?
4. Изоморфизм графа. Даны два графа, являются ли они изоморфными? Другими словами, есть ли взаимо однозначное отображение их вершин, при котором сохранятся рёбра?
Сейчас нет эффективных алгоритмов для этих проблем. Но мы знаем, что первые три находятся и в NP, и в coNP. А значит, если NP ≠ coNP, то они не могут быть NP-полными! А значит, сохраняется вероятность быстрого решения. Аналогичное заключение возможно и для четвёртой проблемы.
P.S. Может показаться, что с факторизацией возникло противоречие. На самом деле нет, и я поправился ранее: доказательство в данном случае означает, что нет решений класса P, и в то же время проблема не NP-полная.
Существует класс coNP — класс P входит и в NP, и в coNP. Если доказано, что NP ≠ coNP, то в coNP не может быть NP-полных проблем.
Приведу некоторые не искусственные проблемы, которые не попадают в класс P и NP-полный:
1. Факторизация целых чисел. Дано целое число, найти простые сомножители.
2. Кратчайший вектор в решётке. Дана решётка L в Rⁿ и целое k, будет ли длина (Евклидова) кратчайшего вектора L находиться в диапазоне [k; kn]?
3. Стохастические игры. Чёрные, Белые и Природа по очереди перемещают фишку по вершинам направленного графа. Природа перемещает случайно. Дан граф, начальная и конечная вершина для фишки. Есть ли у Белых стратегия, которая гарантирует, что фишка достигнет цели с вероятностью ≥ ½?
4. Изоморфизм графа. Даны два графа, являются ли они изоморфными? Другими словами, есть ли взаимо однозначное отображение их вершин, при котором сохранятся рёбра?
Сейчас нет эффективных алгоритмов для этих проблем. Но мы знаем, что первые три находятся и в NP, и в coNP. А значит, если NP ≠ coNP, то они не могут быть NP-полными! А значит, сохраняется вероятность быстрого решения. Аналогичное заключение возможно и для четвёртой проблемы.
P.S. Может показаться, что с факторизацией возникло противоречие. На самом деле нет, и я поправился ранее: доказательство в данном случае означает, что нет решений класса P, и в то же время проблема не NP-полная.
Также в ходе доказательства, судя по всему, доказывается существование односторонней функции.
Функция односторонняя, если она может быть «легко» сосчитана (за полиномиальное время), но в среднем случае «тяжело» обратима (не за полиномиальное время). Существование односторонней функции до сих пор не было доказано. Но есть несколько кандидатов, которые и применяются в криптографии. Если будет доказано, что односторонняя функция существует, то автоматически будет доказано, что P ≠ NP.
Функция односторонняя, если она может быть «легко» сосчитана (за полиномиальное время), но в среднем случае «тяжело» обратима (не за полиномиальное время). Существование односторонней функции до сих пор не было доказано. Но есть несколько кандидатов, которые и применяются в криптографии. Если будет доказано, что односторонняя функция существует, то автоматически будет доказано, что P ≠ NP.
Эта теорема также упоминается в известном комиксе.
Если далее пойти по ссылкам, можно найти классный алгоритм, используемый в Quake II!
думаю, достойно отдельного топика ;)
Был уже отдельный топик с расследованием
А можно, пожалуйста, ссылку? Поиск говорит — странно, ничего не найдено.
Топика возможно и не было, упоминалось в комментариях, вот ссылки на расследование:
Кхм-кхм… Спасибо, но… Мне кажется, или чего-то недопостилось?
Пардон, отправилось раньше времени, хабраюзеры не хотят чтоб я писал чаще раза в час.
www.beyond3d.com/content/articles/8/
www.beyond3d.com/content/articles/15/
www.beyond3d.com/content/articles/8/
www.beyond3d.com/content/articles/15/
Конечно сенсационность была бы при равенстве. :) когда увидел тему топика — глаза округлились! Две задачи тысячелетия за десятилетие — это конечно очень интересно!
Равенство классов P и NP- Гипотеза Ходжа
Гипотеза Пуанкаре- Гипотеза Римана
- Теория Янга — Миллса
- Существование и гладкость решений уравнений Навье — Стокса
- Гипотеза Берча и Свиннертона-Дайера
>>когда увидел тему топика — глаза округлились!
у меня они до сих пор не пришли в обычное состояние =)
чувствую, мой препод по алгоритмам теперь не увидет сна несколько дней по-крайней мере. Он уже запостил у себя в ФБ этот манускрипт и, уверен, ушел в него с головой.
у меня они до сих пор не пришли в обычное состояние =)
чувствую, мой препод по алгоритмам теперь не увидет сна несколько дней по-крайней мере. Он уже запостил у себя в ФБ этот манускрипт и, уверен, ушел в него с головой.
7 проблему Гильберта сам Гильберт считал очень сложной (сложнее теоремы Ферма) и высказывал мнение, что она не будет решена в течении XX века, т.е. потребуется не менее 100 лет. Хотя её решили в течении примерно 30 лет, причем в более обобщенном виде.
Надеюсь мы все доживем до того, как решат все проблемы тысячелетия :)
Надеюсь мы все доживем до того, как решат все проблемы тысячелетия :)
Как студент кафедры «Высшей математики» — вклад этого мужика в науку, если доказательство правильно, просто огромен!
Утопал читать.
Утопал читать.
Достижение важное, но криптографам вздыхать спокойно пожалуй не стоит — неравенство этих классов еще не означает, что не существует полиномиального алгоритма факторизации для обычных компьютеров.
Для квантовых есть уже :)
а что тогда это неравенство означает?
Оно означает, что существуют задачи (например, NP полные), решение которых при наличии подсказки можно проверить за полиномиальное время, но на которых любой полиномиальный алгоритм ошибается хотя бы в одном случае.
Далее встает вопрос о P!=NP в среднем. Если это так, то существует NP-задача, на которой любой полиномиальный алгоритм ошибается «в большей части случаев» (по-моему с вероятностью >2/3 по какой-то там хитрой мере, но точно не помню).
Если P!=NP в среднем, то встает вопрос о существовании односторонней функции. Односторонняя функция — это функция, вычислимая «быстро» (за полиномиальное время), но прообраз «в большей части случаев» «быстро» найти нельзя.
И вот если будет найдена односторонняя функция, то (возможно) криптографы смогут вздохнуть спокойно.
Далее встает вопрос о P!=NP в среднем. Если это так, то существует NP-задача, на которой любой полиномиальный алгоритм ошибается «в большей части случаев» (по-моему с вероятностью >2/3 по какой-то там хитрой мере, но точно не помню).
Если P!=NP в среднем, то встает вопрос о существовании односторонней функции. Односторонняя функция — это функция, вычислимая «быстро» (за полиномиальное время), но прообраз «в большей части случаев» «быстро» найти нельзя.
И вот если будет найдена односторонняя функция, то (возможно) криптографы смогут вздохнуть спокойно.
Я выше описал несколько примеров.
В департаменте начался неофициальный прием ставок среди студентов: верно ли доказательство =)
Консенсуса, естественно, нет, но все сходятся в одном: однозначно мужику респект за то, что взялся за эту проблему.
Консенсуса, естественно, нет, но все сходятся в одном: однозначно мужику респект за то, что взялся за эту проблему.
Да уж, а доказательство большое и терминов куча :( Может замутим коллективный перевод, Хабр?)
ближе к вечеру могу поучаствовать
давайте дождемся официального вердикта, и, если оно верно, с удовольствием поддержу.
да, это естественно :) перевести 100 страниц неправильного доказательства было бы не очень прикольно)
Официальный вердикт будет нескоро. Теперь журнал выделит некоторое количество рецензентов, каждый из них возьмет кусок доказательства и будет тщательно его проверять. Это легко может растянуться на полгода
Его не будет очень долго. Вспомним, что Институт Клэя только в 2010 году согласился с Перельманом и решил присудить премию.
Хотя тут дело поинтереснее будет)
Хотя тут дело поинтереснее будет)
хотя «введение» там довольно любопытное в любом случае и ИМХО заслуживает перевода.
++ идея! я за готов взяться! может быть отдельный топ под это? и каким образом организовать работу? каждый переводит кусок? или что-то типа svn? предлагаю обдумать и включиться!
ну есть блог «Переводы», во первых.
из того, что есть, я знаю notabenoid.com/, там, насколько я понимаю, текст делится на предложения, каждый может перевести по-своему и голосованием выбирается лучший вариант.
Есть translated.by, ничего не знаю про него.
И есть translate.google.com/toolkit — что-то от гугла. Как потыкаю, напишу)
из того, что есть, я знаю notabenoid.com/, там, насколько я понимаю, текст делится на предложения, каждый может перевести по-своему и голосованием выбирается лучший вариант.
Есть translated.by, ничего не знаю про него.
И есть translate.google.com/toolkit — что-то от гугла. Как потыкаю, напишу)
хабро быдло не знает о notabenoid.com/?
Вот уже вроде начали notabenoid.com/book/10309/
Скрестим пальцы за мужика. Надеюсь, он сделал это!
Да значение работы конечно трудно переоценить, особенно для криптографов. Ну чтож буду ждать мнения умных людей и надеятся, что доказательство все же верно.
Ах, Винай… На два дня меня опередил, чертенок!
А вот и виновник торжества:
Агравалю теперь на 200 страницах придется обратное доказывать)
кто в курсе подскажите, это означает что в задаче комивояжера проще проверить все варианты чем решить?
Перевод доводов отсюда: news.ycombinator.com/item?id=1586091
Several points on the question of whether the proof is likely to be correct:
* As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.)
* Therefore a proper assessment is going to take a while. Until then we can only speculate :-)
* While the crank attempts at P =? NP are statistically much more common (http://news.ycombinator.com/item?id=347295), this isn't one of them. The author is a legit computer scientist: www.hpl.hp.com/personal/Vinay_Deolalikar/
* On the other hand he hasn't published much on complexity theory and isn't known in that community. Which is weird but not necessarily a red flag.
* Looking at his papers, it's possible he's been working on this for about 5+ years — he has two threads of research, basic and industrial, and the former line of publications dried up around 2004.
* On the other hand I don't think anyone knew he was working on this. The only known serious effort was by Ketan Mulmuley at U Chicago.
* It has been known that the straightforward combinatorial approaches to P =? NP aren't going to work, and therefore something out of left field was required (http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf). Mulmuley's plan of attack involved algebraic geometry.
* This paper uses statistical physics. This approach doesn't seem to have been talked about much in the community; I found only one blog comment rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.)
* If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier.
* Finally, since the author is using physics-based methods, there's the possibility that he is using something that's a «theorem» in physics even though it is technically only a conjecture and hasn't actually been proven. Physicists are notorious for brushing technicalities under the rug. It would be very unlikely that the author didn't realize that, but still worth mentioning.
* If that is indeed what happened here, but the rest of the proof holds up, then we would be left with a reduction from P != NP to a physics conjecture, which could be very interesting but not ground breaking.
Conclusion: overall, it certainly looks superficially legit. But in non peer reviewed solutions of open problems there's always a high chance that there's a bug, which might or might not be fixable. Even Andrew Wiles's first attempt at FLT had one. So I wouldn't get too excited yet.
Кое-какие мысли о том, корректно ли доказательство:
* Насколько мне известно, данный документ не подвергался неформальной экспертной оценке; о нем никто не говорил на grapevine (видать, научный форум — прим.пер.) (Исправлено: оказывается, что подвергался и кто-то кроме автора сделал его общедоступным)
* Тем не менее, полноценная оценка займет время. До этого момента мы можем только высказывать предположения.
* В то время как попытки доказать P ?= NP статистически довольно часты ( news.ycombinator.com/item?id=347295 — говорится о том, что каждые пару недель кто-нибудь «доказывает» проблему), данное доказательство к ним не отностится. Автор действительно занимается computer science: www.hpl.hp.com/personal/Vinay_Deolalikar/
* С другой стороны, он особо не публиковался по теории сложности, и сообществу об этом не известно. Что, конечно, странно, но не совсем является поводом для подозрений.
* Судя по его записям, он работал более пяти лет — у него есть два направления исследования, основной и промышленный; а последние публикации прекратились около 2004 года.
* С другой стороны, я не думаю, что кто-то знал о его работе над теоремой. Единственное значимое воздействие на него оказывал Ketan Mulmuley в университете Чикаго.
* Известно, что непосредственные комбинаторные подходы к P ?= NP не работают, поэтому потребовались довольно неожиданные идея ( web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf ). План исследования Mulmuley включал алгебраическую геометрию.
* Это доказательство использует статистическую физику. Об этом подходе особо не говорилось в сообществе; я нашел только один комментарий, который упоминает алгоритм обзорного распространения (survey propagation, хз о чем оно, вариант матиндукции)
* Если используемого в доказательстве статистического метода достаточно для решения проблемы P != NP, то есть хороший шанс, что оно привело к доказательству многих меньших проблем до того, как автор добрался до главной.
* В конце концов, поскольку автор использует физические метода, есть вероятность, что он пользовался что-то на подобии «теоремы» в физике, которая на самом деле всего лишь гипотеза и на самом деле не доказана. Физики печально знамениты тем, что они «заметают технические подробности под коврик». То, что автор не осознал этого, было бы, конечно, маловероятно, но все равно стоит упомянуть об этом.
* Если все-таки сказанное в предыдущем пункте случится, а остальное доказательство останется правильным, то мы перейдем от доказательства P!=NP к доказательству физической гипотезы, что, конечно, интересно, но не так революционно.
В итоге: конечно, доказательство выглядит абсолютно верным. Но в доказательствах, не подвергшихся экспертной оценке, всегда есть шанс присутствия бага, который может быть и не исправляем. Даже первая попытка Andrew Wiles по доказательству FLT, содержала ошибку. Поэтому я бы пока что особо не возбуждался по этому поводу.
--Насколько мне известно, данный документ не подвергался неформальной экспертной оценке; о нем -----никто не говорил на grapevine (видать, научный форум — прим.пер.) (Исправлено: оказывается, что -----подвергался и кто-то кроме автора сделал его общедоступным)
grapevine — это сарафанное радио, слухи.
«I heard no talk on the grapevine» — переводится как — «я не слышал никаких разговоров об этом / до меня не доходили никакие слухи об этом».
grapevine — это сарафанное радио, слухи.
«I heard no talk on the grapevine» — переводится как — «я не слышал никаких разговоров об этом / до меня не доходили никакие слухи об этом».
Вообще, извините, но перевод полумашинный.
* С другой стороны, он особо не публиковался по теории сложности, и сообществу об этом не известно. Что, конечно, странно, но не совсем является поводом для подозрений.
* С другой стороны, я не думаю, что кто-то знал о его работе над теоремой. Единственное значимое воздействие на него оказывал Ketan Mulmuley в университете Чикаго.
* С другой стороны, он особо не публиковался по теории сложности, и сообществу об этом не известно. Что, конечно, странно, но не совсем является поводом для подозрений.
* С другой стороны, я не думаю, что кто-то знал о его работе над теоремой. Единственное значимое воздействие на него оказывал Ketan Mulmuley в университете Чикаго.
> Conclusion: overall, it certainly looks superficially legit.
Правильно переводится как «выглядит разумным при поверхносном осмотре», а не «выглядит абсолютно верным».
Правильно переводится как «выглядит разумным при поверхносном осмотре», а не «выглядит абсолютно верным».
Было бы очень странно, если бы оказалось наоборот, что P=NP. Фактически это означало бы, что любую задачу, любой алгоритм можно решить за полиномиальное время (очень быстро), а значит нет никакого смысла в росте скоростей процессоров, построении кластеров и суперкомпьютеров да и вообще в развитии целой кучи областей науки. Но ведь не может же такого быть, чтобы это всё изобреталось зря.
Вы не поняли что такое эффективный алгоритм. Как на обычном компе запустить алгоритм с полиномиальным временем O(n^10000)?
«Да, полином. Но бывают экспоненты лучше, чем этот полином»
всего 10к? а чего так мелко берете? если множество входа например 1М (а бывают и куда больше), то любой с радостью променяет 2^N на N^10k. суть не в том, какое число будет в степени полинома, все равно рано или поздно он станет выгоднее экспоненциального (К.О. :)) конечно бывают случаи, когда вполне можно воспользоваться и экспоненциальным алгоритмом, но это дело практиков, теоретиков проблема волнует в несколько другом контексте.
Китаец уже доказал P = NP, теперь Индус доказал P != NP. Это у них давняя вражда.
Я ничего не понял из топика и из комментариев. Но комментарии прочитал с удовольствием. Приятно, что есть столь увлечённые люди.
Чарли Эппс скептически изучает доказательство.
на 76-й странице ошибка!
А кто кроме криптографов может теперь спать/ворочаться спокойно?
Не может быть чтобы задача тысячелетия имела такой скудный диапазон применения.
Не может быть чтобы задача тысячелетия имела такой скудный диапазон применения.
Я тоже буду спать спокойнее!
В работе, которой сейчас занимаюсь, мы «списали» свои проблемы поиска хорошего алгоритма для одной задачи на трудности поиска эффективного оптимального алгоритма для задач класса NP.
Если доказательство верно, то нас не упрекнут. что мы де слишком ленивые =)
В работе, которой сейчас занимаюсь, мы «списали» свои проблемы поиска хорошего алгоритма для одной задачи на трудности поиска эффективного оптимального алгоритма для задач класса NP.
Если доказательство верно, то нас не упрекнут. что мы де слишком ленивые =)
Я написал несколько примеров выше.
Автору статьи — большое спасибо! Вы (и автор доказательства) спасли нас от очередного топика околоайтишного характера. Жаль что большинство комментариев посвящено вопросам «а че это вообще такое?».
Жаль что на данный момент я вряд ли смогу адекватно полностью прочитать доказательство =(
Жаль что на данный момент я вряд ли смогу адекватно полностью прочитать доказательство =(
Чего стока радости… Огорчаться тут надо ведь… Это же стока задач, потенциально гораздо проще решаемых, будут решаться так же как и всегда! =)
А, кстати, чем закончилась история с этим доказательством? Судя по отсутствию сенсаций с участием NP-полноты за последние года — в доказательстве ошибка?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Опубликовано доказательство P ≠ NP?