Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 73
Я тоже не верю, что P=NP, но подобные доводы никуда не годятся.
А почему не верите Вы?
Скотт Ааронсон, известный доктор Computer Science в MIT, как-то опубликовал 10 аргументов верить, что P ≠ NP. Почитайте, довольно забавно.
Ну да, только у меня на тему P ≠ NP вцелом только самый первый аргумент и он совпадает с первым аргументом в статье. Следующие аргументы больше относятся конкретно к этой попытке.
Спасибо за ссылку, кстати. Мне очень понравился 9-й аргумент, а 10-м я, грубо говоря, пользовался ставя на ошибку в доказательстве свою машину. :)
Спасибо за ссылку, кстати. Мне очень понравился 9-й аргумент, а 10-м я, грубо говоря, пользовался ставя на ошибку в доказательстве свою машину. :)
Много слов, но не понятно на каких условиях поставлен «на кон» автомобиль :)
Какое доказательство вам необходимо, чтобы вы его приняли?
Кто получит автомобиль — автор алгоритма или тот кто подтвердит алгоритм?
Вы выбрали удобную позицию, вряд ли кто-то поставит машину против вашей, да и доказать неправильность алгоритма можно 1 примером — а для доказательства его правильности нужен полный теоретический анализ.
Какое доказательство вам необходимо, чтобы вы его приняли?
Кто получит автомобиль — автор алгоритма или тот кто подтвердит алгоритм?
Вы выбрали удобную позицию, вряд ли кто-то поставит машину против вашей, да и доказать неправильность алгоритма можно 1 примером — а для доказательства его правильности нужен полный теоретический анализ.
Ну, скажем, если автор получит премию института Клэя, я к ней добавлю свою машину.
Против моей машины ничего ставить не нужно, такие условия были бы несправедливы с моей стороны.
Доказательство там достаточно короткое, так что полный теоретический анализ в этом случае — дело относительно простое.
Против моей машины ничего ставить не нужно, такие условия были бы несправедливы с моей стороны.
Доказательство там достаточно короткое, так что полный теоретический анализ в этом случае — дело относительно простое.
Если подобных доводов кому-то достаточно, чтобы поставить на них свою машину, то почему бы и нет? :)
Кстати, вот небольшой список различных доказательств того, что P=NP, P!=NP и неразрешимости этой проблемы.
Так вот, если судоку простой, то вполне возможно, что пользуясь только этими правилами, вы сможете его решить. Но в сложном судоку вам неприменно придётся помимо тупого применения правил разбирать какие-нибудь варианты.
Офигенно доходчивая формулировка P и NP. Аплодирую Вам.
Чур, если что, машина мне :)
>Потому что в последние несколько десятков лет стали известны сотни NP-полных задач, вплоть до задачи об оптимальном алгоритме для игры в сапёра. Достаточно решить хоть одну из этих задач, чтобы все они оказались решены. И тем не менее, несмотря на все усилия тысяч людей, никаких продвижений в сторону создания алгоритмов для этих задач пока не наблюдается.
>… на правдоподобность гипотезы n2 указывал тот факт, что метод умножения «в столбик» известен не менее четырёх тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацуба[3][4][5][6] нашёл новый метод умножения двух n-значных чисел
ru.wikipedia.org/wiki/Умножение_Карацубы
>… на правдоподобность гипотезы n2 указывал тот факт, что метод умножения «в столбик» известен не менее четырёх тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацуба[3][4][5][6] нашёл новый метод умножения двух n-значных чисел
ru.wikipedia.org/wiki/Умножение_Карацубы
В математике вообще было немало неоправдавшихся гипотез. Другое дело, что каждое опровержение гипотезы обычно несёт в себе какую-то свежую идею, которая открывает математикам глаза на механизмы, которые они раньше не замечали.
Что касается умножения, гипотеза, как написано в той же статье, продержалась всего 4 года — совсем не долго. Мне кажется, до того же Колмогорова никто серьёзно не задавался вопросом об ассимптотически более быстром умножении. Просто потому что длинные числа умножали очень редко.
Что касается умножения, гипотеза, как написано в той же статье, продержалась всего 4 года — совсем не долго. Мне кажется, до того же Колмогорова никто серьёзно не задавался вопросом об ассимптотически более быстром умножении. Просто потому что длинные числа умножали очень редко.
>Мне кажется, до того же Колмогорова никто серьёзно не задавался вопросом об ассимптотически более быстром умножении. Просто потому что длинные числа умножали очень редко.
звучит правдоподобно. наверное из-за того, что у меня нету фактов по этому поводу.
>В математике вообще было немало неоправдавшихся гипотез
тем не менее, аргумент в духе «это невозможно, потомучто за N лет никто этого, не придумал» изначальное порочен.
звучит правдоподобно. наверное из-за того, что у меня нету фактов по этому поводу.
>В математике вообще было немало неоправдавшихся гипотез
тем не менее, аргумент в духе «это невозможно, потомучто за N лет никто этого, не придумал» изначальное порочен.
Разумеется, публиковать статью «за 4 30 лет никто не нашел алгоритма, так что его нет» нельзя. В конце концов, за тот же срок никто не доказал, что алгоритма нет.
Но в качестве интуитивного соображения такой довод может быть иногда приемлим. Хотя, безусловно, на него нельзя положиться ни в какой серьезной задаче.
Но в качестве интуитивного соображения такой довод может быть иногда приемлим. Хотя, безусловно, на него нельзя положиться ни в какой серьезной задаче.
С другой стороны, хотя положиться и нельзя — но на практике полагаются. Например, вся современная криптография основана на отсутствии быстрого алгоритма факторизации. Если его вдруг найдут — будет весело.
каким-каким местом накрывается современная криптография от появления квантовых компутеров?
Да-да, тем самым. К счастью пока, кажется, квантовых компьютеров больше чем из 10 кубитов строить не получилось.
Ну и плюс, сейчас стали использовать алгоритмы, отличные от RSA, которые не ломаются квантовым компьютером.
Ну и плюс, сейчас стали использовать алгоритмы, отличные от RSA, которые не ломаются квантовым компьютером.
Тем самым. Взлом RSA, например, становится просто детской забавой. Да и если не ошибаюсь, все (ну или почти все) современные алгоритмы асимметричного шифрования основаны на сложности факторизации.
Другое дело, что непонятно, что будет раньше — квантовый компьютер или решение P=NP.
Другое дело, что непонятно, что будет раньше — квантовый компьютер или решение P=NP.
Не совсем. Во-первых, RSA используется только в протоколах с открытым ключём. Во-вторых, даже в них сейчас всё чаще стали использоваться другие задачи, например ссвязанные с эллиптическими кривыми. Я там в подробности не вдавался, но говорят, что они квантовым компьютерами не ломаются.
Да есть Elliptic Curves, и еще как минимум основнанные на задачи декодирования криптосистемы, которые, если правильно помню, тоже не имеют существенно более быстрых квантовых алгоритмов криптоанализа.
Например системы МакЭлис или Крука. МакЭлис вроде бы особо стойкой не считается, но она тем не менее одна из известных.
Собственно факторизация только предположительно является NP-полной. То есть гипотетически ибез квантов ее можно ломать. Просто все уверены что в ближайшее время никто не додумается до алгоритма. Так в общем-то все криптосистемы работают: «Иван Иваныч, профессор — ломал, ломал, не сломал. Петр Петрович, очень уважаемый человек — ломал, ломал, не сломал. Значит и абы кто наверное так просто не сломает.»
Например системы МакЭлис или Крука. МакЭлис вроде бы особо стойкой не считается, но она тем не менее одна из известных.
Собственно факторизация только предположительно является NP-полной. То есть гипотетически ибез квантов ее можно ломать. Просто все уверены что в ближайшее время никто не додумается до алгоритма. Так в общем-то все криптосистемы работают: «Иван Иваныч, профессор — ломал, ломал, не сломал. Петр Петрович, очень уважаемый человек — ломал, ломал, не сломал. Значит и абы кто наверное так просто не сломает.»
Да, есть Elliptic Curves, и еще, как минимум, основанные на задачЕ декодирования криптосистемы
— прошу прощения, поздно встал :)
ну и далее по тексту прошу прощения )
— прошу прощения, поздно встал :)
ну и далее по тексту прошу прощения )
Если я не ошибаюсь, ни одна из современных криптографических систем не основывается на NP-полной задаче. Так что теоретическая криптография живёт в отрыве от практической.
Ну в общем близко к правде, насколько я могу оценить. Подавляющее большинство теоретико-числовых алгоритмов завязаны либо на факторизацию, либо на дискретный логарифм. NP-полнота их пока не доказана и обе задачи имеют теоретически работающие квантовые алгоритмы.
Кодовые криптосистемы, как я уже говорил, насколько знаю такого алгоритма не имеют, но возможно это пока что просто Фактор Неуловимого Джо. Там внутри теории кодирования есть ряд np-полных задач, вокруг которых и пытаются построить криптосистемы. Но я сейчас от этого очень далек, поэтому абсолютно точно гвоорить не могу. Если вам интересна криптография — очень рекомендую посмотреть самостоятельно.
Кодовые криптосистемы, как я уже говорил, насколько знаю такого алгоритма не имеют, но возможно это пока что просто Фактор Неуловимого Джо. Там внутри теории кодирования есть ряд np-полных задач, вокруг которых и пытаются построить криптосистемы. Но я сейчас от этого очень далек, поэтому абсолютно точно гвоорить не могу. Если вам интересна криптография — очень рекомендую посмотреть самостоятельно.
Я когда учился в университете, слушал по ней отличные спец. курсы. Только с тех пор немного подзабыл, да и за современными трендами не слежу.
Аналогично :)
Только я не спец курсы слушал, а обычные (хотя разницы не вполне понимаю)
а где если не секрет?
Но тоже уже не помню деталей, так как работаю не в этой области, о чем иногда жалею. Поэтому запросто могу в чем-то навратью
Только я не спец курсы слушал, а обычные (хотя разницы не вполне понимаю)
а где если не секрет?
Но тоже уже не помню деталей, так как работаю не в этой области, о чем иногда жалею. Поэтому запросто могу в чем-то навратью
Сам Крук читал?
мне — он :)
Крука не знаю. :) Мне курсы на эти темы читали Матиясевич, Гирш, Оревков.
Никого их этих не знаю. Овчинников или «заяц» были?
Я не думаю, что у нас пересекались множества преподавателей. Всё-таки разные ВУЗы.
Кстати Матиясевича Вы могли бы знать. Он очень известный чувак. Решил в своё время десятую проблему Гильберта.
Кстати Матиясевича Вы могли бы знать. Он очень известный чувак. Решил в своё время десятую проблему Гильберта.
Слава Б-гу, что вопросы веры не рассматриваются наукой.
Проблема в том, что решение сложной задачи редко можно расписать полностью. Поэтому можно считать, что «доказательство — это рассуждение, способное убедить вас в истинности доказываемого утверждения настолько, чтобы вы были готовы убеждать в его истинности других с помощью того же рассуждения» (если не ошибаюсь, Шень).
Да не, многие доказательства можно полностью расписать. См. www.cs.ru.nl/~freek/100/
Слава науке, что научные вопросы УЖЕ не рассматриваются церковью.
По-моему, минусующие не совсем поняли товарища bobermaniac.
Тут обыгрывается слишком частое употребление в околонаучной статье слова «верить» и его производныхФреше.
Да, кстати.
Тут обыгрывается слишком частое употребление в околонаучной статье слова «верить» и его производных
Да, кстати.
После знакомства и изучения проблемы P? NP в университете, у меня сложилось впечатление, что само соотношение классов не является однозначно принципиальным для практического применения. Вся суть NP задач в относительной «сложности» (несворачиваемом многообразии вариантов перебора). И если будет найден полиномиальный алгоритм эта «сложность» должна будет куда-то перейти: либо это будет огромная степень полинома/количества переменных, либо сложные абстрактные понятия, включающие часть сложности «в себя» (и соответсвенно при их сведении к элементарному языку снова приобретающие статус NP).
Все равно чем-то нужно заплатить.
Все равно чем-то нужно заплатить.
Ну, в быстрых алгоритмах для факторизации или, скажем, для умножения, сложность переходит в собственно принципиальную сложность алгоритма, в константный множитель, так сказать. Тем не менее, ими при больших значениях всё равно выгодно пользоваться. При том, что скачок там меньше чем между экспонентой и полиномом.
Кстати, да, это еще один важный вопрос: при каких размерностях задач отдача от более эффективного алгоритма начинает проявляться в полной мере?
Есть мнение, что у каждого языка есть определенный потолок сложности явлений, которые могут быть эффективно описаны им. Соответсвенно, если «сложность» выбранного алгоритма не превосходит этот порог, то может найтись другой более эффрктивный алгоритм на этом языке (может быть так и было с быстрым умножением). Если нет — надо использовать другой язык.
Грубо говоря (этот пример не совсем корректный, но в качестве иллюстрации) использовать квантовые компьютеры вместо обычных.
Есть мнение, что у каждого языка есть определенный потолок сложности явлений, которые могут быть эффективно описаны им. Соответсвенно, если «сложность» выбранного алгоритма не превосходит этот порог, то может найтись другой более эффрктивный алгоритм на этом языке (может быть так и было с быстрым умножением). Если нет — надо использовать другой язык.
Грубо говоря (этот пример не совсем корректный, но в качестве иллюстрации) использовать квантовые компьютеры вместо обычных.
Всё-таки гипотеза Таниямы-Симуры не была построена вокруг теоремы Ферма. Лишь лет через 15 Герхард Фрай доказал, что теорема Ферма следует из этой гипотезы. А Уайлс уже доказывал эту гипотезу.
Я читал тот топик про 3-SAT, но не исследовал. Однако уверен, что алгоритм верный. Ошибку надо искать в области представления данных. Я уверен, что все 3-SAT задачи, которые можно закодировать представленным образом, решаются как положено. Однако должен быть целый пласт непредставимых входных данных.
Я читал тот топик про 3-SAT, но не исследовал. Однако уверен, что алгоритм верный. Ошибку надо искать в области представления данных. Я уверен, что все 3-SAT задачи, которые можно закодировать представленным образом, решаются как положено. Однако должен быть целый пласт непредставимых входных данных.
В области представления данных там всё чисто. Все дизъюнкции разбиваются на группы, в которых они применяются только к подрядстоящим переменным для какой-нибудь перестановки переменных. Потом в таких группах для каждых трёх последовательных переменных выписывается табличка истинности. Собственно всё.
Скорее всего ошибка там в самом алгоритме. Там эти структуры фильтруются по нескольким правилам (как в примере с судоку) и считается, что в результате если решения нет, то они останутся пустыми.
Скорее всего ошибка там в самом алгоритме. Там эти структуры фильтруются по нескольким правилам (как в примере с судоку) и считается, что в результате если решения нет, то они останутся пустыми.
В чём вообще смысл утверждений «я не верю в»? Если решат — это будет мега-прорыв. Если не решат — не будет ничего.
Хуже не станет в любом случае.
В чём смысл антипомощи данному направлению, к тому же фразами типа «я не верю, потому что человечество за всё время существования не смогло летать на аппарате тяжелее воздуха» — подобных аргументов в истории было много очень.
Дайте хоть понадеяться чуть-чуть, пессимистов и так много :-)
Хуже не станет в любом случае.
В чём смысл антипомощи данному направлению, к тому же фразами типа «я не верю, потому что человечество за всё время существования не смогло летать на аппарате тяжелее воздуха» — подобных аргументов в истории было много очень.
Дайте хоть понадеяться чуть-чуть, пессимистов и так много :-)
Если Вам так будет легче, будем считать, что я добавил к премии института Клэя за решение этой задачи свой маленький вклад в размере автомобиля. Только для этой попытки решения, естественно.
Да, и я не говорил в то, что я в принципе не верю в то что эту задачу можно решить в одну или другую сторону. Я просто не верю в то, что это конкретное решение правильное.
Да, и я не говорил в то, что я в принципе не верю в то что эту задачу можно решить в одну или другую сторону. Я просто не верю в то, что это конкретное решение правильное.
> Уж простите за резкость, но вы бы взяли да впрямую проанализировали алгоритм, ежели такой умный :) Раз две-три странички всего :)
Так я это сделал. См. ветку обсуждения начиная с этого комментария. А вот тут я привожу пример на котором, как мне кажется, не должна работать ключевая часть алгоритма. Автор того поста обещал сегодня ответить.
Я не пишу что я опроверг это доказательство потому, что я не уверен на 100% в том что я правильно всё понял. Быть может я что-то упустил и мой контрпример обламывается. В таком случае я буду думать дальше и придумаю следующий.
Теорема Пифагора — плохой пример, так как первые известные её доказательства срезу были простыми. Я говорю о немного другой ситуации. Если есть гипотеза, открытая на протяжении хотя бы несколько десятков лет, то её доказательство будет либо длинным, либо использующим революционные идеи, либо и то и другое.
Со многими фактами из теории чисел, например, была примерно такая история. Ставилась задача, через какое-то время находили её решение. Оно оказывалось очень длинным, но правильным. Потом со временем люди придумывали новые доказательства, использующие более мощные теории из других областей математики, которые оказывались короче.
Кстати, ТРИЗ не применим к математике. Точнее, некоторые его части применимы, но они-то как раз известны математикам уже на протяжении тысячелетий.
Так я это сделал. См. ветку обсуждения начиная с этого комментария. А вот тут я привожу пример на котором, как мне кажется, не должна работать ключевая часть алгоритма. Автор того поста обещал сегодня ответить.
Я не пишу что я опроверг это доказательство потому, что я не уверен на 100% в том что я правильно всё понял. Быть может я что-то упустил и мой контрпример обламывается. В таком случае я буду думать дальше и придумаю следующий.
Теорема Пифагора — плохой пример, так как первые известные её доказательства срезу были простыми. Я говорю о немного другой ситуации. Если есть гипотеза, открытая на протяжении хотя бы несколько десятков лет, то её доказательство будет либо длинным, либо использующим революционные идеи, либо и то и другое.
Со многими фактами из теории чисел, например, была примерно такая история. Ставилась задача, через какое-то время находили её решение. Оно оказывалось очень длинным, но правильным. Потом со временем люди придумывали новые доказательства, использующие более мощные теории из других областей математики, которые оказывались короче.
Кстати, ТРИЗ не применим к математике. Точнее, некоторые его части применимы, но они-то как раз известны математикам уже на протяжении тысячелетий.
Как и обещал, продолжение здесь: habrahabr.ru/blogs/computer_science/112337/
В статье Википедии есть ссылка на сайт, где приведены 91 доказательство теоремы Пифагора. И редко какое из них не помещается на экран. Нечего там растягивать на 200 страниц, если не вводить ненужные сущности.
Еще в той же статье Википедии есть ссылка на другую статью: ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BB%D0%B8%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0#.C2.AB.D0.A4.D0.B5.D1.80.D0.BC.D0.B0.D1.82.D0.B8.D1.81.D1.82.D1.8B.C2.BB
Кроме того, широко известного доказательства, других, менее известных и более коротких в открытом доступе нет. И еще есть тысячи некорректных. Или скажете, что все развитие математики в последние лет 100-150 было попыткой все сделать «круто» через усложнение? Конечно, сейчас надо изучить немало книг, чтобы разбираться в серьезных современных работах. Не проще ли вместо построения сложных многоуровневых абстракций использовать несколько методов, которые понятны любому школьнику, и утверждать, что с их помощью можно красиво расписать все явления во вселенной? А какую тему раскрыл ТРИЗ? Какие крупные открытия были сделаны с использованием ТРИЗ?
Простые вещи — должны, примитивные — нет.
Еще в той же статье Википедии есть ссылка на другую статью: ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BB%D0%B8%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0#.C2.AB.D0.A4.D0.B5.D1.80.D0.BC.D0.B0.D1.82.D0.B8.D1.81.D1.82.D1.8B.C2.BB
Кроме того, широко известного доказательства, других, менее известных и более коротких в открытом доступе нет. И еще есть тысячи некорректных. Или скажете, что все развитие математики в последние лет 100-150 было попыткой все сделать «круто» через усложнение? Конечно, сейчас надо изучить немало книг, чтобы разбираться в серьезных современных работах. Не проще ли вместо построения сложных многоуровневых абстракций использовать несколько методов, которые понятны любому школьнику, и утверждать, что с их помощью можно красиво расписать все явления во вселенной? А какую тему раскрыл ТРИЗ? Какие крупные открытия были сделаны с использованием ТРИЗ?
Простые вещи — должны, примитивные — нет.
М. То есть все используют теорию, но (какие нехорошие!) не упоминают о ее использовании?
Атата! Может, к нарушению авторских прав приравняем? :)
В моем комментарии не было ни слова про доказательство P=NP. Ни про одно.
И да, я будут рад, если мне щелкнут по носу, подтвердив корректность доказательства.
Атата! Может, к нарушению авторских прав приравняем? :)
В моем комментарии не было ни слова про доказательство P=NP. Ни про одно.
И да, я будут рад, если мне щелкнут по носу, подтвердив корректность доказательства.
Вы делаете выводы, которые касаются всей науки в целом, приводите в качестве примера теоремы, относящиеся к математике, а не к Computer Science.
Я ваши выводы комментирую, вы утверждаете, что топик перепутал я.
Так?
Я ваши выводы комментирую, вы утверждаете, что топик перепутал я.
Так?
> — Автор топика назвал обсуждаемый алгоритм для np-полной задачи «простым» и за это его критикует
> — Я в своём комментарии написал, что простотые решения = хорошие решения
Я критикую не за простоту. Я просто замечаю, что если бы простое решение существовало, то оно бы уже было найдено.
> — Я в своём комментарии написал, что простотые решения = хорошие решения
Я критикую не за простоту. Я просто замечаю, что если бы простое решение существовало, то оно бы уже было найдено.
Просто для заметки.
1. Подобного представления формул (в виде компактных троек) еще ни у кого не было — это оригинальный подход.
2. Сама идея и алгоритм были придуманы и описаны 10 лет назад. Просто почему-то ее никто до этого не замечал. Владимир Федорович занимался решением этой задачи независимо от своей основной работы, ни в рамках какого-то научного проекта, а просто так — как хобби (кстати начал он ее еще в 90-х). У нас на кафедре про его работу знали, но за рамки кафедры эти знания так и не вышли, если не считать единичных публикаций в вузовских сборниках и переписок один-на-один с рецензентами, которые привели к статье в непрофильном журнале.
Тот факт, что про эту статью узнали сейчас — это чистая случайность. Если бы не нашумевшая история о Деолаликаре, то прошло бы еще 10 лет и так ничего бы не изменилось. Именно эта история сыграла для меня решающую роль. Как так! Его статью обсудили и знают, а о статье Романова за 10 лет так никто и не узнал. Только из-за этого я решил потратить несколько месяцев работы, чтобы вместе с Романовым еще раз перечитать его статью, отредактировать английский вариант, сделать версию в LaTeX (это вообще отдельная история), разобраться в алгоритме, написать реализацию, написать письмо, найти адреса ученых и отправить это письмо им. Но это все было как хобби. Работа никем не спонсировалось, все делалось в свободное время. (Вообще-то я думал на это уйдет меньше времени.) А что получается в итоге? В итоге все уже сыты по-горло подобными доказательствами и я прекрасно понимаю, почему ни у кого нет желания разбираться в этой работе и понимаю скепсицизм с которым к работе относятся.
Судить не мне, но я считаю, что лучше, чтобы о статье узнали поздно чем никогда. А уж верна она или нет — покажет время. Хорошо, что ее уже включили в знаменитый список The P-versus-NP page. Правда под номером 65 и с датой 20 ноября, хотя должны бы были включить в первую пятерку или десятку и с годом 2002.
1. Подобного представления формул (в виде компактных троек) еще ни у кого не было — это оригинальный подход.
2. Сама идея и алгоритм были придуманы и описаны 10 лет назад. Просто почему-то ее никто до этого не замечал. Владимир Федорович занимался решением этой задачи независимо от своей основной работы, ни в рамках какого-то научного проекта, а просто так — как хобби (кстати начал он ее еще в 90-х). У нас на кафедре про его работу знали, но за рамки кафедры эти знания так и не вышли, если не считать единичных публикаций в вузовских сборниках и переписок один-на-один с рецензентами, которые привели к статье в непрофильном журнале.
Тот факт, что про эту статью узнали сейчас — это чистая случайность. Если бы не нашумевшая история о Деолаликаре, то прошло бы еще 10 лет и так ничего бы не изменилось. Именно эта история сыграла для меня решающую роль. Как так! Его статью обсудили и знают, а о статье Романова за 10 лет так никто и не узнал. Только из-за этого я решил потратить несколько месяцев работы, чтобы вместе с Романовым еще раз перечитать его статью, отредактировать английский вариант, сделать версию в LaTeX (это вообще отдельная история), разобраться в алгоритме, написать реализацию, написать письмо, найти адреса ученых и отправить это письмо им. Но это все было как хобби. Работа никем не спонсировалось, все делалось в свободное время. (Вообще-то я думал на это уйдет меньше времени.) А что получается в итоге? В итоге все уже сыты по-горло подобными доказательствами и я прекрасно понимаю, почему ни у кого нет желания разбираться в этой работе и понимаю скепсицизм с которым к работе относятся.
Судить не мне, но я считаю, что лучше, чтобы о статье узнали поздно чем никогда. А уж верна она или нет — покажет время. Хорошо, что ее уже включили в знаменитый список The P-versus-NP page. Правда под номером 65 и с датой 20 ноября, хотя должны бы были включить в первую пятерку или десятку и с годом 2002.
Я понимаю причину вашего недоверия и я тоже заинтересован в проверке правильности доказательства.
Многие в Иинтернете обратили внимание на публикацию только из-за наличия открытого исходного кода, хотя я бы не хотел, чтобы о статье судили по реализации алгоритма. Реализация может помочь в понимании того, что написано в статье. В реализации могут быть баги, которые могут быть никак не связаны с доказательством. Их, конечно, тоже надо искать и исправлять — но это совершенно другая история.
Поиск изъянов исходя из анализа доказательства — это хороший подход. Я очень рад, что нашлись компетентные люди, которые обратили на доказательство внимание. Я постараюсь всячески содействовать в разъяснении положений статьи. Я буду стараться ответить на вопросы исходя из своего понимания и по необходимости буду привлекать В.Ф. Романова.
Многие в Иинтернете обратили внимание на публикацию только из-за наличия открытого исходного кода, хотя я бы не хотел, чтобы о статье судили по реализации алгоритма. Реализация может помочь в понимании того, что написано в статье. В реализации могут быть баги, которые могут быть никак не связаны с доказательством. Их, конечно, тоже надо искать и исправлять — но это совершенно другая история.
Поиск изъянов исходя из анализа доказательства — это хороший подход. Я очень рад, что нашлись компетентные люди, которые обратили на доказательство внимание. Я постараюсь всячески содействовать в разъяснении положений статьи. Я буду стараться ответить на вопросы исходя из своего понимания и по необходимости буду привлекать В.Ф. Романова.
А я не верю в Иисуса, тоже надо-бы отпоститься на эту тему…
«кроме статьи про алгоритм существует его работающая реализация»
Где?
Где?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Почему я не верю в простые алгоритмы для NP-полных задач