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

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

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

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

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

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

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

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

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

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

Что такое конвергенция у невропатолога? И что значит замедленная Конвергенция? Конвергенция у невропатолога на приеме
- 09.05.2026 12:42

Итоги недели 4-10 мая: главные новости Украины и мира Эта неделя стала одним из наиболее насыщенных по к
- 09.05.2026 12:35

Підсумки тижня 4-10 травня: головні новини України та світу Цей тиждень став одним із найбільш насичених за кількістю важливих політичних
- 09.05.2026 12:31

У Чорнобильській зоні пожежі: яка загроза радіації для Києва та України? розбираємо докладно! Чому пожежа поширюється так швидко?
- 09.05.2026 11:37

Трамп допустив продовження перемир’я між Україною та Росією після 9-11 травня Президент Сполучених Штатів Donald Trump заявив, що оголошене короткострокове
- 09.05.2026 11:31

Новини Чернівців 4-10 травня Однією з головних тем тижня у Чернівцях стали питання безпеки та повітряних тривог
- 08.05.2026 12:37

Как оцифровать трудовую книжку самостоятельно и избежать типичных ошибок Вы в Украине или за границей и Нужна помощь онлайн?
- 06.05.2026 12:05

У чому суть прокрастинації і чи так це погано Фраза «Я подумаю про це завтра», яку колись вимовила
- 06.05.2026 11:57

Ціни на пальне на автозаправних станціях пішли вгору Найбільше зростання торкнулося бензину марки А-95.
- 04.05.2026 13:46

Що таке конвергенція у невропатолога? І що означає уповільнена Конвергенція?
- 04.05.2026 12:50

Всі новини