Как стать автором
Обновить

Комментарии 38

Я, может, слепой, или очень глупый, но не нашёл, где показывается полиномиальность «алгоритма».

P.S. А оформление и правда не ахти.
Страница 18, пункт 6
НЛО прилетело и опубликовало эту надпись здесь
Оформление примерно такое же, как у того индуса, только иллюстрации не цветные. Что не помешало индусу прогреметь на весь мир.
А что мешает с 2007 года
— опубликовать более детальную статью,
— исправить недочеты в форматировании,
— опубликовать препринт (например, на arxiv.org/),
— получить какие-либо отзывы от российских коллег-математиков,
— опубликовать свою реализацию алгоритма,
— привести графики скорости экспериментальных вычислений в зависимости от длины входа, из которых будет видно, что алгоритм действительно работает с полиномиальной скоростью?

Сговор?
Насколько я знаю, эта чехарда с рецензентами идет раньше чем с 2007 года и все недочеты с форматированием (лишние запятые, кавычки и прочее) уже давно исправлены. Просто работу никак не хотят признавать.

Не знаю почему нет отзывов от российских коллег-математиков… может быть они и есть? Уточню, напишу позже.

Реализация алгоритма не держится в секрете. Я не занимался реализацией, поэтому не могу сказать достаточно ли материала статьи, чтобы его запрограммировать, но, думаю, достаточно. Кстати, если я правильно помню, реализация появилась как раз в результате общения с рецензентами, чтобы подтвердить полиномиальность и безошибочность алгоритма. Поэтому в статье и появился пункт 7 «Апробация алгоритма и выводы». Не думаю что исходники реализации могут сыграть какую-то важную роль, хотя для независимой оценки может быть будут полезны. Я попробую их достать и выложить где-нибудь здесь.

Никакого сговора, конечно, нет. Я могу предположить что проблема в том, что из нашего окружения никто подобные материалы никогда не публиковал и не знает что и как нужно делать.

Я уверен на 100%, что если бы Владимиру Федоровичу было 30-40 лет он бы нашел способ как добиться публикации. Видимо когда вам за 60 все становится не так просто.

P.S.
Насчет arxiv.org — обязательно передам, тем более, что английский вариант уже должен быть.
> Просто работу никак не хотят признавать.
Это неправильная постановка проблемы. Вопрос надо ставить так, что верна ли изложенная в статье теория? Если нет, то в чем ошибки. Если да, что какие недочеты надо исправлять.

Есть институты РАН, математические факультеты и кафедры в ведущих вузах России, в которых должны быть специалисты, разбирающиеся в теории разрешимости задач, которые могут составить компетентное мнение о научной состоятельности и ценности данной статьи.

Есть иностранные специалисты, занимающиеся подобными проблемами, которые вполне открыто обсуждают математические вопросы и имеют необходимую экспертизу — см. к примеру обсуждение статьи индуса ;)

Уверен, математики весьма заинтересованы в установлении истин и разрешении открытых вопросов. А редакторы серьезных математических журналов наврядли бы отвергли действительно прорывную работу по математике.

Насчет отзывов от коллег-математиков, есть только один отзыв от математика, достаточно общий, который был нужен, чтобы статью приняли в этот журнал.

У вас есть опыт публикации статьи на arxiv.org? С первого просмотра я не смог там найти формы отправки публикации. Можете посодействовать?
Опыта нет, но там нужно зарегистрироваться сначала (наверху справа login).
>> Реализация алгоритма не держится в секрете.

Пусть выложит реализацию алгоритма в свободный доступ. Из статьи очень сложно понять что он делает, из кода будет проще.
статья очень мутная не удивлён, что её не приняли никуда.
уже на второй странице перестаешь понимать что и как он строит. привел бы описание алгоримтма в виде псевдокода, тогда сразу стало бы все понятно.
поверь, 97% статей по математике (в том числе в области сложности алгоритмов) выглядят так же мутно
поверь, я за шесть лет на мехмате успел много статей прочитать, поэтому мне есть, с чем сравнивать.
[OFF]за 6 лет? :) «универ — не школа, за 10 лет не закончишь» (с) или это с учетом начатой аспирантуры?[/OFF]

просто мой не богатый опыт показывает, что на уровне идеи все в математике «очевидно» и в некоторой степени красиво, но как только суть доходит до строгого и формального описания (да еще и в короткие сроки и известно за какие деньги), то чаще всего получаются какие-то мутные схемы, введение каких-то запутывающих обозначений и пр. (и это все не считая описок и мелких косяков)

вот сравни как, например, написаны учебники мат. анализа.
за более, чем 300 лет отточили все мутные схемы и все четко и ясно
того же требовать от статьи не имеет смысла, так что пусть все это остается на совести автора

да и кстати, у вас есть свои статьи? можете их выложить почитать? я, честно говоря, очень удивлюсь, если там будет все гладко и чисто
а где в статье про NP сложность?
Решаемая задача 3-SAT является классическим примером NP-задачи.
а может это просто задачу неправильно классифицировали ранее, так как способа решения не было?
*facepalm* способов решения уйма, только сложность у них не полиномиальная.

почитайте что ли в википедии, что такое класс NP и что-такое NP-полнота.
извините конечно, но у меня математическое высшее образование, и чтото мне из этого образования подсказывает что NP-полнота может быть недоказанная а предположенная. К примеру такими задачами сейчас считаются «необратимые» функции. Причем их необратимость только предполагаемая. А уж то что до сих пор нет доказательства NP=P или NP!=P
NP-полнота задачи означает, что математически любая задача из NP может быть полиномиально сведена к данной. Все. Вот это как раз очень даже доказывается. NP-полные задачи между собой эквивалентны.

А дальше уже другой момент: есть P-задачи, для которых известны полиномиальные алгоритмы и есть другие задачи из NP, для которых такие алгоритмы не известны. То есть если вы придумаете полиномиальный алгоритм для любой NP-полной задачи, то вы автоматически докажете, что NP=P.

См. к примеру, www.intuit.ru/department/algorithms/algomodex/5/ и www.intuit.ru/department/algorithms/algomodex/6/

>> но у меня математическое высшее образование, и чтото мне из этого образования подсказывает

3-SAT проходят в курсе теории алгоритмов на матмехе. Там все доказывается. Это одна из базовых NP-полных задач.

>> К примеру такими задачами сейчас считаются «необратимые» функции

кем считаются? вами?

я вам по секрету сообщу, что сама «необратимая» функция вычисляется эффективно за полиномиальное время, а вот обратная к ней, как раз предполагается, сложно вычислимой, не вычислимой за полиномиальное время. однако никто не предполагает, что задача вычисления обратной функции является NP-полной.

существование «необратимой» функции f само по-себе будет означать, что P != NP, поскольку задача вычисления f^-1 очевидно принадлежит NP, но не принадлежит P. и полнота или неполнота этой задачи не имеет ну совершенно никакого значения.
вы не заметили у себя то самое слово «предполагается»? :)
я не заметил у себя слов «предполагается NP-полнота».
> но у меня математическое высшее образование, и чтото мне из этого образования подсказывает что NP-полнота может быть недоказанная а предположенная.

Может, конечно, быть и предположенная. А у 3-выполнимости, как и у многих других задач, она доказанная.

Наврядли, насколько я понимаю, в общем случае доказано, что задачу выполнимости булевых формул, можно свести к 3-ВЫП, а для самой задачи выполнимости показано, что в общем случае она является NP-полной (собственно, с нее все и началось, см. en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem).
по ссылке вообще нечто другое, доказал что любую NP задачу можно за полиноминальное время проверить на булевой машине. Каким образом это относится к статье? Проверка не есть решение.
Там доказательство, что задача выполнимости булевой функции является NP-полной. Это к вопросу о классификации.
нет :) там доказано что можно построить автомат проверяющий за полиноминальное время, и дальнейшее расширение Карпом с определеним что задачи проверяемые таким образом являются NP-полными :) но ничего об отсутствии какого либо простого способа решения нет :)
А никто и не говорит о наличии или отсутствии простого решения. Это не вопрос классификации.
как раз вопрос :) изза того самого полиноминального времени сведения которое дано в определении :) надо ДОКАЗАТЬ что нет ничего лучше чем полиноминальное.
А чем вам полиномиальное время сведения не нравится? Что может быть лучше? Константа? :D
Если есть статья на английском, то самое очевидное — поступить так же, как Деолаликар. То есть послать статью конкретно специалистам в этой области. Тому же Куку, Разборову… А посылать на Хабр, чтобы вызвать резонанс в научных кругах — довольно странная идея.
Есть статья на английском (я обновил пост). Я не в курсе, куда отправил Деолаликар экземпляр. Можете дать email'ы, или другой способ, кому можно отправить?
Кук: 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 указан на странице.
По разговору с Романовым я выяснил, что есть приложение (написанное на Delphi), в котором реализован алгоритм. Но он был сделан на скорую руку. Возможно прийдется его немного порефакторить. В следующий понедельник я постараюсь взять это приложение и опубликовать исходники. Когда выложу — напишу здесь.
спасибо! выкладывайте и не рефакторенное, поможем с рефакторингом =)
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.