SAT
E-mail:
Существует ли полиномиальный алгоритм для решения задачи ВЫПОЛНИМОСТИ?
Мирон Иванович Тельпиз на своём сайте mit.tarusa.ru утверждает, что такой алгоритм есть, и на его сайте даже выложена статья «NP-полнота, суперприведение и проблема четырех красок» (подготовлена для печати в журнале «Известия Российской академии наук. Серия математическая», отдана в редакцию журнала 19.01.03г), в которой приведён этот самый алгоритм и оценка его сложности.
А вот рецензия на эту статью Александра А. Разборова (Математический институт РАH им. Стеклова, член редколлегии Известий РАH): оригинал отзыва в формате PostScript, и форматы PDF, Word8, HTML.
Кстати, ссылки на некоторые статьи А. А. Разборова приведены в списке литературы на сайте М. И. Тельпиза.
Мои замечания относительно статьи:
1. В алгоритме (стр. 11 – 12) важное значение имеет только пункт 6 б), т. к. остальные пункты — это элементарные упрощения формул.
Именно пункт 6 б) при увеличении размерности задачи n и будет почти всё время выполняться, именно там и будет ветвление.
И вот, как сказано в алгоритме, именно «в случае 6 б) записываем T или T* (строго говоря, выбор является произвольным, но следует его указать в алгоритме)».
Это по сути означает, что мы для проверки задачи выполнимости берём произвольно значение соответствующей переменной равным 1 или 0,
и если при текущем наборе значений переменных получаем 0, то в дальнейшем у нас значение этой переменной поменяется на противоположное
и т. д. попадаем на ветвление по другой переменной, если снова в результате получаем 0, то может быть возврат к ветвлению по предыдущей переменной
и т. д. получается полный перебор.
2. В статье не доказано, что алгоритм не зациклится.
3. Ошибка скорее всего где-то в теоремах 3 или 4 (стр. 27 – 28). Кто хочет, — проверьте алгоритм на таблицах задачи ВЫП для принципа Дирихле.
А что же думают другие специалисты по поводу тельпизовского доказательства P=NP и вообще о сложности проблемы P=?=NP?
Ю. В. Матиясевич (тот, который доказал неразрешимость десятой проблемы Гильберта) по слухам по этому поводу с улыбкой ответил: «а, очередная ерунда».
А вот выдержка из
интервью
Дональда Кнута:
Вопрос: Знаете ли вы, "P=NP" уже доказано? Ходят слухи, что это так.
Кнут: Что именно вы слышали?
Вопрос: Что-то из России.
Кнут: Из России? Это новость для меня. Я не думаю, что кто-то
уже доказал это. Но, я знаю, Энди Яо (Andy Yao) надеется решить эту
задачу в ближайшие пять-десять лет. Он вдохновлен Эндрю Уайлсом
(Andrew Wiles), посвятившим семь лет доказательству Последней Теоремы
Ферма. Они оба из Принстона. Если кто и способен сделать это,
то это Энди.
Три или четыре года назад появилась статья в китайском журнале, в
которой один профессор заявлял что способен решить NP-сложную задачу
за полиномиальное время. Он рассматривал задачу о кликах, и
использовал очень хитрый способ их представления. Метод
предположительно работал за полиномиальное время, но реально требовал
что-то порядка n12 шагов, так что было невозможно его
проверить уже при n=5. Поэтому было очень сложно искать ошибки в его
доказательстве. Я поехал в Стэнфорд и засел за него с нашими
дипломниками, и нам потребовалась пара часов, чтобы найти ошибку.
Я написал автору письмо об этом, и еще через пару месяцев он
ответил, что "нет, нет, там нет ошибки". Я решил больше с этим не
связываться. Я сделал свою часть работы. Но я не верю, что эта
задача решена. Это самая сложная задача из стоящих сегодня перед
современной теоретической информатикой, а возможно, и всей
современной наукой.
Н. П. Варновский
(из статьи Проблема P =? NP, классы сложностей и криптография,
эта статья также доступна здесь:
HTML
и CHM):
«Теперь о проблеме соотношения классов P и NP.
На данный момент она является одной из наиболее важных и наиболее
популярных нерешенных математических проблем. С сожалением приходится
констатировать, что проблема эта стала даже слишком популярной. Не
будет большим преувеличением сказать, что ферматисты XXI века
доказывают, что P=NP. Работы с такими "доказательствами" публикуются
регулярно и, как правило, несут на себе печать "синдрома непризнанного
гения": безудержное самовосхваление, претензии на какие-то выдающиеся
открытия, позволяющие одним махом решить все мировые проблемы, и,
главное, отсутствие корректных определений и доказательств. Гораздо
реже "доказательства" утверждения публикуются достаточно
квалифицированными математиками, просто допустившими какой-либо
просмотр в своих рассуждениях. И уж совсем редко встречаются работы,
в которых предпринимаются попытки (также несостоятельные) доказать,
что P≠NP».
Ссылки
Позиционная алгебра логики
Miron Telpiz's P=NP Page — сайт М. И. Тельпиза
М.И. Тельпиз «О принципе позиционности в логических преобразованиях» — доклад М. И. Тельпиза (презентация, фотографии, аудиозапись) 20.09.2001 в Институте космических исследований РАН.
Математическая страница — сайт Владимира Тарасова из команды М. И. Тельпиза
Форум, организованный В. Тарасовым
Интернет-магазин urss.ru, книга № 24175
— здесь за 999 руб. можно купить книгу Мирона Тельпиза
«Принцип позиционности для счисления и исчисления функций. Том первый».
Первая часть книги,
главы 1-4, страницы 1-140
Список литературы из книги,
страницы 449-452
Нижние оценки для алгоритмов выполнимости
Eli Ben-Sasson, Avi Wigderson. Short Proofs are Narrow — Resolution made Simple. 25.04.2002 PS PDF
Ссылки из рецензии:
[1] P. Beame and T. Pitassi. Propositional proof complexity: Past, present and future. Technical Report TR98-067, Electronic Colloquium on Computational Complexity, 1998. Available at ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1998/TR98-067/index.html.
[2] A. Haken. The intractability or resolution. Theoretical Computer Science, 39:297-308, 1985.
[3] P. Beame and T. Pitassi. Simplified and improved resolution lower bounds. In Proceedings of the 37th IEEE FOCS, pages 274-282, 1996. Also available at http://www.cs.washington.edu/homes/beame/papers/clause.ps.
Алгоритмы выполнимости
М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов. Алгоритмы для пропозицональной выполнимости и верхние оценки их сложности (Записки научных семинаров ПОМИ, Том 277, 2001 г., стр. 14-46)
Прочее
Тема на beon.ru
«Re: М. И. Тельпиз и доказательство P=NP»,
которая является продолжением такой же темы
из эхоконференции RU.SCIENCE сети Fidonet.
В одном из сообщений говорится, что найдена ошибка в алгоритме Тельпиза.
Тема «P=NP Позиционная алгебра логики» на mathforum.ru
Таблицы задачи ВЫП для принципа Дирихле — там я привёл таблицы ВЫП для 3 и 4 клеток (для большего числа клеток n таблицы строятся аналогично). Принцип Дирихле рекомендую как лучший способ для проверки на полиномиальность тельпизовских алгоритмов решения задачи выполнимости булевых формул. Обратите внимание, что при увеличении n отношение количества строк с 2 непустыми клетками к количеству остальных строк таблицы стремится к бесконечности, т. е. с увеличением n почти все FS-операторы задачи ВЫП будут иметь ранг 2, что по мнению Тельпиза (смотрите 7а) О криптографической защите информации) говорит о том, что получается задача ВЫП не самой большой сложности.
Сайт находится в стадии развития