SAT


Поиск по сайту        Найти: на

E-mail:

Гостевая книга
Пишите сюда, если у Вас есть какие-либо вопросы, пожелания, предложения или какая-либо другая интересная информация по тематике сайта, которая будет интересна всем.
Предложения о "РАСКРУТКЕ" сайта и прочий спам будут беспощадно удаляться!

Форум
Предназначен для обсуждений по тематике сайта.
Всё, что не по теме, будет удаляться! Если хотите обратиться к создателю этого сайта, пишите в гостевую книгу, или на e-mail, если Ваше сообщение предназначено исключительно создателю сайта.


Существует ли полиномиальный алгоритм для решения задачи ВЫПОЛНИМОСТИ?

Мирон Иванович Тельпиз на своём сайте www.tarusa.ru/~mit утверждает, что такой алгоритм есть, и на его сайте даже выложена статья «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

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

Ссылки из рецензии:

[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.
В одном из сообщений говорится, что найдена ошибка в алгоритме Тельпиза.

Тема на turgor.ru

Тема «P=NP Позиционная алгебра логики» на mathforum.ru

Таблицы задачи ВЫП для принципа Дирихле — там я привёл таблицы ВЫП для 3 и 4 клеток (для большего числа клеток n таблицы строятся аналогично). Принцип Дирихле рекомендую как лучший способ для проверки на полиномиальность тельпизовских алгоритмов решения задачи выполнимости булевых формул. Обратите внимание, что при увеличении n отношение количества строк с 2 непустыми клетками к количеству остальных строк таблицы стремится к бесконечности, т. е. с увеличением n почти все FS-операторы задачи ВЫП будут иметь ранг 2, что по мнению Тельпиза (смотрите 7а) О криптографической защите информации) говорит о том, что получается задача ВЫП не самой большой сложности.


Сайт находится в стадии развития

Хостинг от uCoz