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

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

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

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

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

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

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

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

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

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

Новый год:2025 время перезагрузки и новых надежд Для кого-то это повод подвести итоги, для других – попытка
- 21.11.2024 14:56

Як заброньованому виїхати за кордон? З початком дії воєнного стану в Україні запроваджено обмеження на перетин
- 15.11.2024 13:14

КиївПрайд: скандал через співпадіння з Днем пам’яті жертв Голодомору Співпадіння дат: проблема етики чи випадковість?
- 15.11.2024 12:27

У Чернівцях за клопотанням слідчих поліції взято під варту місцевого наркозбувача Здійснюючи превентивні поліцейські заходи на території міста Чернівці, правоохоронці з
- 08.11.2024 11:46

Дональд Трамп одержал победу 2024 Победа Трампа также привела к усилению позиций
- 06.11.2024 14:48

Психологічна допомога для чоловіків Чому за допомогою звертаються чоловіки
- 31.10.2024 22:58

За допомогу в перетині кордону чоловікам - засудили на 2 роки тюрми Відповідно до вироку Новоселицького районного суду Чернівецького району, двох
- 31.10.2024 11:40

Какие черты лица у мужчин и женщин, которые изменяют? Выяснилось, что изменщиков можно отличить по определенным типичным чертам лица
- 30.10.2024 09:01

Введено спрощений алгоритм переведення військових Новий алгоритм спрощує процедуру переведення військовослужбовців
- 29.10.2024 16:37

Огляд основних воєнних дій в Україні з 21 по 27 жовтня Союзники та партнери підтримують Україну
- 29.10.2024 09:25

Всі новини