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

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

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

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

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

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

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

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

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

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

Ціни на воду можуть зрости в кілька разів у 2026 році: що відомо та чому ситуація критична Чому водоканали опинилися на межі
- 11.08.2025 13:35

Цены на воду могут вырасти в несколько раз в 2026 году: что известно и почему ситуация критическая Уже в 2026 году украинцы могут столкнуться с резким ростом тарифов на воду.
- 08.08.2025 13:37

Курс долара знижується другий день поспіль Євро — 48,2854 грн (зростання на 19,4 копійки).
- 06.08.2025 16:58

Покровск почти отрезан от внешнего мира: гуманитарная помощь не поступает. В настоящее время в Покровске находится около 1 370 жителей
- 06.08.2025 14:15

Яке свято 7 серпня? сь які свята та пам'ятні дати припадають на цей день в Україні:
- 06.08.2025 13:28

Покровськ майже відрізаний від зовнішнього світу: гуманітарна допомога не надходить Наразі у Покровську перебуває близько 1 370 мешканців
- 06.08.2025 13:15

Трамп запровадив 25% мита проти Індії через її енергетичну співпрацю з Росією Трамп наголосив, що вжиття жорсткіших економічних заходів, зокрема щодо країн, які підтримують торгівлю з Росією, є необхідним кроком.
- 06.08.2025 13:11

Трамп подписал указ о введении 25% пошл доп пошлин на товары из Индии
- 06.08.2025 10:13

Що таке моя IP-адреса Як дізнатися свою IP-адресу?
- 04.08.2025 20:29

Стрілянина у Харкові: ветеран з протезом зазнав поранення після нападу Напад зафіксували очевидці
- 03.08.2025 14:15

Всі новини