ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Stanislav Shwartsman                 2:400/520      01 Apr 2002  21:17:32
 To : Sergei Katkovsky
 Subject : P = NP!
 -------------------------------------------------------------------------------- 
 

 
 01 Apr 02 06:48, you wrote to All:
 
  SK> ===
  SK>                РЕВОЛЮЦИЯ В КРИПТОГРАФИИ И HЕ ТОЛЬКО
 
  [skipped]
 
  SK> ===
 
  SK> Взято с сайта www.compusterva.ru
 
  Все посмотрели на сегодняшнее число и на источник информации ! :)
 
  А если серьезно, то вот отрывок из форума "Ответы на все вопросы",
  Дональда Кнута, для тех, кого этот вопрос действительно интересует.
 
  === Cut Here ==
 Вопрос: Знаете ли вы, "P=NP" уже доказано? Ходят слухи, что это так.
 
 Кнут: Что именно вы слышали?
 
 Вопрос: Что-то из России.
 
 Кнут: Из России? Это новость для меня. Я не думаю, что кто-то уже доказал это.
 о, я знаю, Энди Яо (Andy Yao) надеется решить эту задачу в ближайшие пять-десять
 лет. Он вдохновлен Эндрю Уайлсом (Andrew Wiles), посвятившим семь лет
 доказательству Последней Теоремы Ферма. Они оба из Принстона. Если кто и
 способен сделать это, то это Энди.
 
 Три или четыре года назад появилась статья в китайском журнале, в которой один
 профессор заявлял что способен решить NP-сложную задачу за полиномиальное время.
 Он рассматривал задачу о кликах, и использовал очень хитрый способ их
 представления. Метод предположительно работал за полиномиальное время, но
 реально требовал что-то порядка n^12 шагов, так что было невозможно его
 проверить уже при n=5. Поэтому было очень сложно искать ошибки в его
 доказательстве. Я поехал в Стэнфорд и засел за него с нашими дипломниками, и нам
 потребовалась пара часов, чтобы найти ошибку. Я написал автору письмо об этом, и
 еще через пару месяцев он ответил, что "нет, нет, там нет ошибки". Я решил
 больше с этим не связываться. Я сделал свою часть работы. о я не верю, что эта
 задача решена. Это самая сложная задача из стоящих сегодня перед современной
 теоретической информатикой, а возможно, и всей современной наукой.
  === Cut Here ==
 
     E-mail: gate@fidonet.org.il
     Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
 
 Bye !
 Stanislav     (AKA Night's Man)                        [Team Technion]
 ---
  * Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    P = NP!   Sergei Katkovsky   01 Apr 2002 06:48:18   P = NP!   Stanislav Shwartsman   01 Apr 2002 21:17:32   P = NP!   Andrey Arnold   01 Apr 2002 23:00:14   P = NP!   Alexander Topolskiy   06 Apr 2002 01:03:26   С первым апреля!   voodoochile   01 Apr 2002 12:11:32   Re: P = NP!   Valentin Davydov   01 Apr 2002 17:57:16   P = NP!   Alexander Shmidt   01 Apr 2002 12:35:15   P = NP!   Comoderator Of Ru Algorithms   01 Apr 2002 19:37:45