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

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

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

      Читать дальше →
    • AnjLab.SyncIT — синхронизируем свои задачи с Microsoft Outlook

        Коллективная работа немыслима без средств, позволяющих управлять задачами, распределять их между участниками команды, отслеживать изменения. Для этого используются модули трэкинга задач таких популярных систем коллективной работы, как Trac, Team Foundation Server, Salesforce и т.д. В то же время, человеку удобнее хранить все свои задачи, как личные, так и служебные, в персональном органайзере на своем компьютере или КПК. Для этой цели хорошо подходит MS Outlook 2007.

        Между этими подходами нет противоречия, задача в том, чтобы синхронизировать «коллективное» и «персональное» хранилища задач. Эта проблема может быть решена с помощью нашей разработки SyncIT. Это маленькая программа, постоянно запущенная в system tray, которая периодически загружает информацию о новых \ изменившихся задачах из «коллективного» хранилища в «персональное» — список задач Outlook 2007. При этом, сам Outlook может быть не запущен.


        Читать дальше →
      • Работа с Java в командной строке

        Сейчас уже никто не создает программы в консоли. Используя любимую IDE, разработчик чувствует себя неуютно за чужим компьютером, где её нет.
        Решив разобраться в работе Ant и Maven, я поймал себя на том, что не смогу собрать приложение без них в консоли.
        В данной статье я постарался уместить все этапы проектирования демонстрационного приложения, чтобы не искать справку по каждой команде на просторах Интернета.
        Читать дальше →
      • Обсуждение работы алгоритма Романова на примере

          В продолжение вчерашнего обсуждения.

          В прошлый раз остановились на том, чтобы объяснить как работают алгоритмы унификации и фильтрации на конкретном примере. Сам пример был построен особым образом, чтобы проверить определенные свойства алгоритмов.

          Для дальнейшего обсуждения я написал небольшой unit-тест, который оперирует формулой из примера. Unit-тест нужен для того, чтобы пропустить шаг алгоритма Романова, где происходит декомпозиция исходной формулы на множество CTF. Вместо этого декомпозиция предлагается изначально автором вопроса.

          Unit-тест и подробный лог работы приложения я выложил здесь:

          gist.github.com/791064

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

          Как видно из лога работы, тест заканчивается ситуацией, когда на очередном шаге построения гиперструктуры базисный граф оказался пустым множеством, что согласно алгоритму означает, что формула не выполнима (пункт 2b внизу страницы 11 в тексте статьи).

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

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

            Примерно полгода назад, в августе 2010-го была опубликована попытка доказать что P≠NP. Тогда один математик-блогер, Скотт Оронсон, чтобы не казаться голословным в своём недоверии к этому доказательству поставил свой дом на то, что доказательство окажется ошибочным. Пожалуй, я ничего не потеряю если последую (с меньшим размахом) его примеру и поставлю на то, что нынешний алгоритм неправилен свой автомобиль (Auris 2008-го года выпуска).

            По-моему, Оронсон немного рисковал. Винод Деолаликар, автор того доказательства — относительно известный математик, задача P≠NP входит в область его компетенции, и само доказательство использовало несколько принципиально новых идей, дающих надежду на то, что с помощью них удастся обойти трудности, с которыми сталкивались те кто пытался доказать этот факт до него. С нынешним доказательством ситуация немного иная.
            Читать дальше →
          • Открытое письмо ученым и эталонная реализация алгоритма Романова для NP-полной задачи 3-ВЫП

              С момента предыдущей публикации о полиномиальном алгоритме Романова для 3-ВЫП прошло 4,5 месяца.

              За это время мы с Владимиром Федоровичем подготовили вариант статьи, чтобы отправить его коллегам-ученым и попутно реализовали эталонную реализацию этого алгоритма на Java.
              Читать дальше →
            • О проблеме продвижения научных работ и исследований

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

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

                Автор статьи, конечно же, мог бы более подробно описать суть работы, рассказать об авторе, привести ссылки на его другие работы, монографии и т.д. Но проблема, о которой он говорит, существует и о ней никто не говорит. У меня были похожие ситуации, поэтому немного поделюсь опытом и своими соображеними.
                Читать дальше →
              • Всё (или почти всё) о пробеле

                  Как следует из заголовка, речь в статье пойдёт о неотъемлемой части любого русскоязычного (и не только) текста — о пробеле. Мы затронем историю пробела, виды пробелов, вопросы употребления пробела в веб-типографике.

                  Вообще говоря, пробел — это любое пустое место в рукописном, печатном или отображаемом на любом другом носителе тексте. Так что пробелы бывают разные:
                  • спусковые (большие вертикальные пропуски в первой полосе издания) и концевые пробелы полосы,
                  • абзацные отступы и концевые пробелы абзаца,
                  • межстрочные пробелы (между строками текста),
                  • межсловные пробелы (между словами в одной строке),
                  • межбуквенные пробелы (между буквами в слове).
                  Далее речь пойдёт о межсловных пробелах, разделяющих слова, и функционально принадлежащих к знакам препинания.
                  Читать дальше →