Платинова Буковина

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

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

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

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

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

Источник: www.lenta.ru

Додати свій коментарій:

*Ім'я:
E-mail:
*Коментарій:	Символів залишилося: із
Підтвердіть, що Ви людина  Відповідь - одне слово на тій же мові, що й питання. Відповідь на питання «скільки» - число Нову загадку, будь-ласка

Другие новости:

Гель-лак: запорука ідеального манікюру Важко уявити, але ще десятки років тому манікюр був зовсім іншим і
- 21.11.2025 09:00

Гринчук подала у відставку: відомо хто тимчасово очолить Міністерство енергетики 12 листопада стало відомо, що міністр енергетики України Світлана Гринчук написала
- 19.11.2025 14:58

За минулу добу шахраї ошукали буковинців на майже 187000 гривень Троє громадян стали жертвами псевдобанкірів, двоє
- 19.11.2025 13:42

Бонді: Мін'юст США опублікує документи у справі Епштейна протягом 30 днів Як передає Report з посиланням на Reuters, про це
- 18.11.2025 16:37

Призначено в.о. міністра юстиції України - це Людмила Сугак 19 листопада уряд ухвалив рішення призначити Людмилу Сугак
- 18.11.2025 15:13

Заява Кремля про Трампа та війну в Україні Кремль видав нову цинічну заяву щодо Трампа та війни проти України
- 17.11.2025 15:55

Військовий з Буковини разом із спільником організував канал переправлення чоловіків до Європи Під час чергової спроби незаконного переправлення обидва
- 14.11.2025 22:30

Новое заявление Кремля о Трампе и войне в Украине Кремль выдал новое циничное заявление о Трампе
- 14.11.2025 22:07

Суть скандала вокруг Энергоатома простыми словами Что такое дело Энергоатома — просто о главном
- 14.11.2025 14:04

Суть корупційної справи навколо Енергоатому простими словами Як саме це працювало
- 14.11.2025 13:00

Всі новини