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

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

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

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

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

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

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

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

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

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

У Чернівцях стартує опалювальний сезон: тепло подадуть з 4 листопада З 4 листопада у Чернівцях офіційно розпочнеться опалювальний
- 03.11.2025 17:07

Лише в окремих регіонах: графіки відключення світла на 4 листопада Заклик до громадян
- 03.11.2025 16:24

ЗСУ тиснуть під Добропіллям: наступ українських військ змушує росіян відтягувати сили з Покровська Українська армія продовжує активні наступальні дії на Добропільському
- 03.11.2025 15:38

Программа УЗ-3000: кому достанется бесплатная поездка по железной дороге и почему не всем
- 03.11.2025 15:00

Корабель інопланетян чи звичайна комета прилетить у листопаді? Як було виявлено об’єкт 3I/ATLAS
- 03.11.2025 14:54

Програма УЗ-3000: кому дістанеться безкоштовна поїздка залізницею і чому не всім В “Укрзалізниці” розповіли, як працюватиме нова соціальна ініціатива — програма “УЗ-3000”
- 03.11.2025 14:48

Команда США приїде до України для узгодження спільної дронової програми Уже наступного тижня до України прибуде представницька делегація зі
- 03.11.2025 12:02

Чернігів під небом тривоги: як живе місто, де темрява стала звичною Чернігів не спить. Навіть коли здається, що
- 30.10.2025 21:35

Корабль инопланетян прилетит в ноябре? Астрофизики предупреждают о загадочном объекте, который
- 30.10.2025 15:02

Російські ракети залетіли на Буковину з боку Румунії: деталі нічної атаки
- 30.10.2025 12:08

Всі новини