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

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

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

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

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

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

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

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

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

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

Уже цими вихідними українці можуть відчути скорочення тривалості відключень світла Свириденко зазначила, що зараз ключовим завданням є формування
- 12.12.2025 10:51

Як налаштувати себе на успіх У ритмі алгоритму. Чи можливо налаштувати мозок на успіх?
- 11.12.2025 15:08

Рютте зробив заяву про можливі строки мирної угоди та необхідність «перевірити Путіна» Генеральний секретар НАТО Марк Рютте заявив, що саме
- 11.12.2025 14:53

Де шукати юридичний захист постраждалим від домашнього насильства Як розпізнати, що йдеться саме про домашнє насильство
- 10.12.2025 20:37

Коломойский сделал громкое заявление: на Миндича было совершено покушение в Израиле. Во время рассмотрения апелляции относительно собственной меры пресечения Коломойский
- 10.12.2025 15:43

Коломойський зробив гучну заяву: на Міндіча було здійснено замах в Ізраїлі. Коломойський зробив гучну заяву: на Міндіча було здійснено замах в Ізраїлі.
- 10.12.2025 15:25

Як діяти при погрозах або переслідуванні в соцмережах Перш за все, важливо усвідомити: будь-які погрози в інтернеті — це
- 09.12.2025 14:31

Як не втратити себе в гонитві за ілюзіями - ідеали в житті людей Неідеальні ідеали, або Як не втратити себе в гонитві за ілюзіями
- 08.12.2025 13:26

4 фишки iPhone, о которых стоит знать перед покупкой Как выбрать iPhone
- 08.12.2025 11:18

Росія продовжує атакувати Україну дронами: де загроза ударів сьогодні ввечорі? Обстріли та наслідки
- 07.12.2025 20:43

Всі новини