anonymous@RULINUX.NET~# Last login: 2024-12-23 18:26:36
Регистрация Вход Новости | Разметка | Пользователи | Галерея | Форум | Статьи | Неподтвержденное | Трекер | Правила форума | F.A.Q. | Ссылки | Поиск
[#] [Добавить метку] [Редактировать]
Скрыть

Математик заявил о решении одной из задач тысячелетия

\Ъ[  http://lenta.ru/news/2010/08/11/np/ ]{

Индийский математик Винэй Деолаликар (Vinay Deolalikar) представил доказательства решения одной из так нызываемых задач тысячелетия, - ученый опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны. Препринт статьи в формате pdf можно скачать здесь, коротко о работе пишет New Scientist.

Вопрос о равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук о шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?

Доказательство, что классы сложности P и NP не равны, означает, что ответы на представленные выше два вопроса будут отрицательными. Иными словами, проверка шифра и его подбор являются задачами разного класса сложности.

В настоящее время экспертное сообщество не вынесло однозначного мнения по поводу статьи Деолаликара. Стоит ожидать, что оценки других математиков относительно строгости и правомерности доказательства начнут появляться после того, как будет опубликован окончательный вариант статьи. Планируется, что это произойдет в течение недели.

Задачи тысячелетия - это семь задач, за решение каждой из которых математический институт Клэя предлагает приз размером в один миллион долларов. Одной из таких задач было доказательство гипотезы Пуанкаре. Приз за решение этой задачи был присужден российскому математику Григорию Перельману, который, однако, отказался от денег, аргументировав это тем, что не согласен с решением института Клэя.

}

Tux-oid(*) (2010-08-11 12:39:00)

Mozilla/5.0 (X11; U; Linux i686; ru; rv:1.9.2.6) Gecko/20100626 SUSE/3.6.6-1.2 Firefox/3.6.6

[Ответить на это сообщение]
avatar
Скрыть

Re: Математик заявил о решении одной из задач тысячелетия

>Вопрос о равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти?
>Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?
>Доказательство, что классы сложности P и NP не равны, означает, что ответы на представленные выше два вопроса будут отрицательными
мне почему-то всегда казалось это очевидным

anonymous(*)(2010-08-11 15:50:25)

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.8) Gecko/20100723 PCLinuxOS/1.9.2.8-2pclos2010 (2010) Firefox/3.6.8
avatar
Скрыть

Re: Математик заявил о решении одной из задач тысячелетия

>мне почему-то всегда казалось это очевидным
Ну так вот это и надо было ДОКАЗАТЬ с научной точки зрения.

Tux-oid(*)(2010-08-11 15:53:49)

Mozilla/5.0 (X11; U; Linux i686; ru; rv:1.9.2.6) Gecko/20100626 SUSE/3.6.6-1.2 Firefox/3.6.6
avatar
Скрыть

Re: Математик заявил о решении одной из задач тысячелетия

Ну, вопросы математической строгости -- это как бы проблемы проверки результата на соответствие некоторому канону. Вообщем-то, весь 18 век все пользовались интегральным и дифференциальным исчислением Ньютона-Лейбница и особо не парились вопросами его каноничности. Время от времени, правда, возникали дискуссии по поводу актуальной бесконечности, но эти дискуссии затрагивали узкий круг философов, пока остальные проектировали паровые машины и токарные станки с крестовым суппортом. Ну, а в начале 19 века Коши, правда, дал строгое обоснование диф. исчислению, но это была уже не новость ...

geekkoo(*)(2010-08-11 16:05:45)

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.4) Gecko/20070601 SeaMonkey/1.1.2
avatar
Скрыть

Поспешили объявить!

 http://kolokolca.livejournal.com/67206.html

anonymous(*)(2010-08-11 18:52:02)

Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US) AppleWebKit/533.4 (KHTML, like Gecko) Chrome/5.0.375.125 Safari/533.4
Этот тред читают 1 пользователь:
Анонимных: 1
Зарегистрированных: 0




(c) 2010-2020 LOR-NG Developers Group
Powered by TimeMachine

Valid HTML 4.01 Transitional Правильный CSS!