Comments 38
UFO just landed and posted this here
Оформление примерно такое же, как у того индуса, только иллюстрации не цветные. Что не помешало индусу прогреметь на весь мир.
0
А что мешает с 2007 года
— опубликовать более детальную статью,
— исправить недочеты в форматировании,
— опубликовать препринт (например, на arxiv.org/),
— получить какие-либо отзывы от российских коллег-математиков,
— опубликовать свою реализацию алгоритма,
— привести графики скорости экспериментальных вычислений в зависимости от длины входа, из которых будет видно, что алгоритм действительно работает с полиномиальной скоростью?
Сговор?
— опубликовать более детальную статью,
— исправить недочеты в форматировании,
— опубликовать препринт (например, на arxiv.org/),
— получить какие-либо отзывы от российских коллег-математиков,
— опубликовать свою реализацию алгоритма,
— привести графики скорости экспериментальных вычислений в зависимости от длины входа, из которых будет видно, что алгоритм действительно работает с полиномиальной скоростью?
Сговор?
0
Насколько я знаю, эта чехарда с рецензентами идет раньше чем с 2007 года и все недочеты с форматированием (лишние запятые, кавычки и прочее) уже давно исправлены. Просто работу никак не хотят признавать.
Не знаю почему нет отзывов от российских коллег-математиков… может быть они и есть? Уточню, напишу позже.
Реализация алгоритма не держится в секрете. Я не занимался реализацией, поэтому не могу сказать достаточно ли материала статьи, чтобы его запрограммировать, но, думаю, достаточно. Кстати, если я правильно помню, реализация появилась как раз в результате общения с рецензентами, чтобы подтвердить полиномиальность и безошибочность алгоритма. Поэтому в статье и появился пункт 7 «Апробация алгоритма и выводы». Не думаю что исходники реализации могут сыграть какую-то важную роль, хотя для независимой оценки может быть будут полезны. Я попробую их достать и выложить где-нибудь здесь.
Никакого сговора, конечно, нет. Я могу предположить что проблема в том, что из нашего окружения никто подобные материалы никогда не публиковал и не знает что и как нужно делать.
Я уверен на 100%, что если бы Владимиру Федоровичу было 30-40 лет он бы нашел способ как добиться публикации. Видимо когда вам за 60 все становится не так просто.
P.S.
Насчет arxiv.org — обязательно передам, тем более, что английский вариант уже должен быть.
Не знаю почему нет отзывов от российских коллег-математиков… может быть они и есть? Уточню, напишу позже.
Реализация алгоритма не держится в секрете. Я не занимался реализацией, поэтому не могу сказать достаточно ли материала статьи, чтобы его запрограммировать, но, думаю, достаточно. Кстати, если я правильно помню, реализация появилась как раз в результате общения с рецензентами, чтобы подтвердить полиномиальность и безошибочность алгоритма. Поэтому в статье и появился пункт 7 «Апробация алгоритма и выводы». Не думаю что исходники реализации могут сыграть какую-то важную роль, хотя для независимой оценки может быть будут полезны. Я попробую их достать и выложить где-нибудь здесь.
Никакого сговора, конечно, нет. Я могу предположить что проблема в том, что из нашего окружения никто подобные материалы никогда не публиковал и не знает что и как нужно делать.
Я уверен на 100%, что если бы Владимиру Федоровичу было 30-40 лет он бы нашел способ как добиться публикации. Видимо когда вам за 60 все становится не так просто.
P.S.
Насчет arxiv.org — обязательно передам, тем более, что английский вариант уже должен быть.
0
> Просто работу никак не хотят признавать.
Это неправильная постановка проблемы. Вопрос надо ставить так, что верна ли изложенная в статье теория? Если нет, то в чем ошибки. Если да, что какие недочеты надо исправлять.
Есть институты РАН, математические факультеты и кафедры в ведущих вузах России, в которых должны быть специалисты, разбирающиеся в теории разрешимости задач, которые могут составить компетентное мнение о научной состоятельности и ценности данной статьи.
Есть иностранные специалисты, занимающиеся подобными проблемами, которые вполне открыто обсуждают математические вопросы и имеют необходимую экспертизу — см. к примеру обсуждение статьи индуса ;)
Уверен, математики весьма заинтересованы в установлении истин и разрешении открытых вопросов. А редакторы серьезных математических журналов наврядли бы отвергли действительно прорывную работу по математике.
Это неправильная постановка проблемы. Вопрос надо ставить так, что верна ли изложенная в статье теория? Если нет, то в чем ошибки. Если да, что какие недочеты надо исправлять.
Есть институты РАН, математические факультеты и кафедры в ведущих вузах России, в которых должны быть специалисты, разбирающиеся в теории разрешимости задач, которые могут составить компетентное мнение о научной состоятельности и ценности данной статьи.
Есть иностранные специалисты, занимающиеся подобными проблемами, которые вполне открыто обсуждают математические вопросы и имеют необходимую экспертизу — см. к примеру обсуждение статьи индуса ;)
Уверен, математики весьма заинтересованы в установлении истин и разрешении открытых вопросов. А редакторы серьезных математических журналов наврядли бы отвергли действительно прорывную работу по математике.
+1
Насчет отзывов от коллег-математиков, есть только один отзыв от математика, достаточно общий, который был нужен, чтобы статью приняли в этот журнал.
У вас есть опыт публикации статьи на arxiv.org? С первого просмотра я не смог там найти формы отправки публикации. Можете посодействовать?
У вас есть опыт публикации статьи на arxiv.org? С первого просмотра я не смог там найти формы отправки публикации. Можете посодействовать?
0
>> Реализация алгоритма не держится в секрете.
Пусть выложит реализацию алгоритма в свободный доступ. Из статьи очень сложно понять что он делает, из кода будет проще.
Пусть выложит реализацию алгоритма в свободный доступ. Из статьи очень сложно понять что он делает, из кода будет проще.
+1
статья очень мутная не удивлён, что её не приняли никуда.
уже на второй странице перестаешь понимать что и как он строит. привел бы описание алгоримтма в виде псевдокода, тогда сразу стало бы все понятно.
уже на второй странице перестаешь понимать что и как он строит. привел бы описание алгоримтма в виде псевдокода, тогда сразу стало бы все понятно.
+2
поверь, 97% статей по математике (в том числе в области сложности алгоритмов) выглядят так же мутно
0
поверь, я за шесть лет на мехмате успел много статей прочитать, поэтому мне есть, с чем сравнивать.
0
[OFF]за 6 лет? :) «универ — не школа, за 10 лет не закончишь» (с) или это с учетом начатой аспирантуры?[/OFF]
просто мой не богатый опыт показывает, что на уровне идеи все в математике «очевидно» и в некоторой степени красиво, но как только суть доходит до строгого и формального описания (да еще и в короткие сроки и известно за какие деньги), то чаще всего получаются какие-то мутные схемы, введение каких-то запутывающих обозначений и пр. (и это все не считая описок и мелких косяков)
вот сравни как, например, написаны учебники мат. анализа.
за более, чем 300 лет отточили все мутные схемы и все четко и ясно
того же требовать от статьи не имеет смысла, так что пусть все это остается на совести автора
да и кстати, у вас есть свои статьи? можете их выложить почитать? я, честно говоря, очень удивлюсь, если там будет все гладко и чисто
просто мой не богатый опыт показывает, что на уровне идеи все в математике «очевидно» и в некоторой степени красиво, но как только суть доходит до строгого и формального описания (да еще и в короткие сроки и известно за какие деньги), то чаще всего получаются какие-то мутные схемы, введение каких-то запутывающих обозначений и пр. (и это все не считая описок и мелких косяков)
вот сравни как, например, написаны учебники мат. анализа.
за более, чем 300 лет отточили все мутные схемы и все четко и ясно
того же требовать от статьи не имеет смысла, так что пусть все это остается на совести автора
да и кстати, у вас есть свои статьи? можете их выложить почитать? я, честно говоря, очень удивлюсь, если там будет все гладко и чисто
0
а где в статье про NP сложность?
0
Решаемая задача 3-SAT является классическим примером NP-задачи.
0
а может это просто задачу неправильно классифицировали ранее, так как способа решения не было?
-3
*facepalm* способов решения уйма, только сложность у них не полиномиальная.
почитайте что ли в википедии, что такое класс NP и что-такое NP-полнота.
почитайте что ли в википедии, что такое класс NP и что-такое NP-полнота.
+3
извините конечно, но у меня математическое высшее образование, и чтото мне из этого образования подсказывает что NP-полнота может быть недоказанная а предположенная. К примеру такими задачами сейчас считаются «необратимые» функции. Причем их необратимость только предполагаемая. А уж то что до сих пор нет доказательства NP=P или NP!=P
0
NP-полнота задачи означает, что математически любая задача из NP может быть полиномиально сведена к данной. Все. Вот это как раз очень даже доказывается. NP-полные задачи между собой эквивалентны.
А дальше уже другой момент: есть P-задачи, для которых известны полиномиальные алгоритмы и есть другие задачи из NP, для которых такие алгоритмы не известны. То есть если вы придумаете полиномиальный алгоритм для любой NP-полной задачи, то вы автоматически докажете, что NP=P.
См. к примеру, www.intuit.ru/department/algorithms/algomodex/5/ и www.intuit.ru/department/algorithms/algomodex/6/
А дальше уже другой момент: есть P-задачи, для которых известны полиномиальные алгоритмы и есть другие задачи из NP, для которых такие алгоритмы не известны. То есть если вы придумаете полиномиальный алгоритм для любой NP-полной задачи, то вы автоматически докажете, что NP=P.
См. к примеру, www.intuit.ru/department/algorithms/algomodex/5/ и www.intuit.ru/department/algorithms/algomodex/6/
+1
>> но у меня математическое высшее образование, и чтото мне из этого образования подсказывает
3-SAT проходят в курсе теории алгоритмов на матмехе. Там все доказывается. Это одна из базовых NP-полных задач.
>> К примеру такими задачами сейчас считаются «необратимые» функции
кем считаются? вами?
я вам по секрету сообщу, что сама «необратимая» функция вычисляется эффективно за полиномиальное время, а вот обратная к ней, как раз предполагается, сложно вычислимой, не вычислимой за полиномиальное время. однако никто не предполагает, что задача вычисления обратной функции является NP-полной.
существование «необратимой» функции f само по-себе будет означать, что P != NP, поскольку задача вычисления f^-1 очевидно принадлежит NP, но не принадлежит P. и полнота или неполнота этой задачи не имеет ну совершенно никакого значения.
3-SAT проходят в курсе теории алгоритмов на матмехе. Там все доказывается. Это одна из базовых NP-полных задач.
>> К примеру такими задачами сейчас считаются «необратимые» функции
кем считаются? вами?
я вам по секрету сообщу, что сама «необратимая» функция вычисляется эффективно за полиномиальное время, а вот обратная к ней, как раз предполагается, сложно вычислимой, не вычислимой за полиномиальное время. однако никто не предполагает, что задача вычисления обратной функции является NP-полной.
существование «необратимой» функции f само по-себе будет означать, что P != NP, поскольку задача вычисления f^-1 очевидно принадлежит NP, но не принадлежит P. и полнота или неполнота этой задачи не имеет ну совершенно никакого значения.
0
> но у меня математическое высшее образование, и чтото мне из этого образования подсказывает что NP-полнота может быть недоказанная а предположенная.
Может, конечно, быть и предположенная. А у 3-выполнимости, как и у многих других задач, она доказанная.
Может, конечно, быть и предположенная. А у 3-выполнимости, как и у многих других задач, она доказанная.
0
Наврядли, насколько я понимаю, в общем случае доказано, что задачу выполнимости булевых формул, можно свести к 3-ВЫП, а для самой задачи выполнимости показано, что в общем случае она является NP-полной (собственно, с нее все и началось, см. en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem).
0
по ссылке вообще нечто другое, доказал что любую NP задачу можно за полиноминальное время проверить на булевой машине. Каким образом это относится к статье? Проверка не есть решение.
0
Там доказательство, что задача выполнимости булевой функции является NP-полной. Это к вопросу о классификации.
0
нет :) там доказано что можно построить автомат проверяющий за полиноминальное время, и дальнейшее расширение Карпом с определеним что задачи проверяемые таким образом являются NP-полными :) но ничего об отсутствии какого либо простого способа решения нет :)
0
Если есть статья на английском, то самое очевидное — поступить так же, как Деолаликар. То есть послать статью конкретно специалистам в этой области. Тому же Куку, Разборову… А посылать на Хабр, чтобы вызвать резонанс в научных кругах — довольно странная идея.
+6
Есть статья на английском (я обновил пост). Я не в курсе, куда отправил Деолаликар экземпляр. Можете дать email'ы, или другой способ, кому можно отправить?
0
Кук: www.cs.toronto.edu/~sacook/
Карп: www.eecs.berkeley.edu/~karp/
Разборов: people.cs.uchicago.edu/~razborov/
Рудич: www.cs.cmu.edu/~rudich/
Липтон: rjlipton.wordpress.com/ (e-mail rjl@cc.gatech.edu)
Ааронсон: scottaaronson.com/
Это те, кто приходит в голову в первую очередь. У всех, кроме Липтона, e-mail указан на странице.
Карп: www.eecs.berkeley.edu/~karp/
Разборов: people.cs.uchicago.edu/~razborov/
Рудич: www.cs.cmu.edu/~rudich/
Липтон: rjlipton.wordpress.com/ (e-mail rjl@cc.gatech.edu)
Ааронсон: scottaaronson.com/
Это те, кто приходит в голову в первую очередь. У всех, кроме Липтона, e-mail указан на странице.
0
По разговору с Романовым я выяснил, что есть приложение (написанное на Delphi), в котором реализован алгоритм. Но он был сделан на скорую руку. Возможно прийдется его немного порефакторить. В следующий понедельник я постараюсь взять это приложение и опубликовать исходники. Когда выложу — напишу здесь.
0
Продолжение здесь: habr.ru/p/112161/
0
Sign up to leave a comment.
Сведение решения NP-полной задачи «3-выполнимость» к алгоритму с полиномиальной сложностью