SAT
E-mail:
Гостевая книга
Пишите сюда, если у Вас есть какие-либо вопросы, пожелания, предложения или
какая-либо другая интересная информация по тематике сайта,
которая будет интересна всем.
Предложения о "РАСКРУТКЕ" сайта и прочий спам будут беспощадно удаляться!
Форум
Предназначен для обсуждений по тематике сайта.
Всё, что не по теме, будет удаляться!
Если хотите обратиться к создателю этого сайта,
пишите в гостевую книгу, или на e-mail, если Ваше сообщение предназначено
исключительно создателю сайта.
Существует ли полиномиальный алгоритм для решения задачи ВЫПОЛНИМОСТИ?
Мирон Иванович Тельпиз на своём сайте www.tarusa.ru/~mit утверждает, что такой алгоритм есть, и на его сайте даже выложена статья «NP-полнота, суперприведение и проблема четырех красок» (подготовлена для печати в журнале «Известия Российской академии наук (Серия математическая)», отдана в редакцию журнала 19.01.03г), в которой приведён этот самый алгоритм и оценка его сложности.
А вот рецензия на эту статью Александра А. Разборова (Математический институт РАH им. Стеклова, член редколлегии Известий РАH): оригинал отзыва в формате PostScript, и форматы PDF, Word8, HTML.
Кстати, ссылки на некоторые статьи А. А. Разборова приведены в списке литературы на сайте М. И. Тельпиза.
А что же думают другие специалисты по поводу тельпизовского доказательства 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.
В одном из сообщений говорится, что найдена ошибка в алгоритме Тельпиза.
Таблицы задачи ВЫП для принципа Дирихле
Сайт находится в стадии развития