Пользователь
0,0
рейтинг
31 августа 2010 в 14:06

Сведение решения NP-полной задачи «3-выполнимость» к алгоритму с полиномиальной сложностью

По следам публикации P != NP (для которой, кстати, опубликовано опровержение), хочу поделиться ссылкой на статью В.Ф. Романова, в которой он показывает, как можно свести решение NP-полной задачи «3-ВЫП» к полиномиальному алгоритму.

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



image Владимир Федорович Романов, профессор кафедры ИСИМ Владимирского государственного университета, уже несколько лет пытается опубликовать свою работу в журналах с высоким уровнем авторитета, но рецензенты попросту не хотят брать на себя ответственность и публиковать эту работу, постоянно мотивируя отказы нелепыми придирками к форматированию. Для меня это выглядит смешно, потому что более педантичного человека, чем профессор Романов, я не встречал.

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

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

Неортодоксальные комбинаторные модели
на основе несогласованных структур
Романов В.Ф. (romvf@mail.ru)
Владимирский государственный университет

http://zhurnal.ape.relarn.ru/articles/2007/143.pdf

Обновление от 01.09.2010

Сегодня беседовал с Владимиром Федоровичем.

Оказывается английская версия статьи лежит рядом:

Non-orthodox combinatorial models based on discordant
structures
Romanov V. F. (romvf@mail.ru)
Vladimir state university

http://zhurnal.ape.relarn.ru/articles/2007/143e.pdf
dmitrygusev @dmitrygusev
карма
13,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.