Скачать или смотреть Математические «миры» криптографии: в каком из них мы живем?

В течение сорока лет Рассел Импальяццо работал на переднем крае теории сложности вычислений, изучая внутреннюю сложность различных задач. Самый известный открытый вопрос в этой области, называемый проблемой P и NP, заключается в том, являются ли многие, казалось бы, сложные вычислительные задачи на самом деле простыми при использовании правильного алгоритма. Ответ на этот вопрос имел бы далеко идущие последствия для науки и безопасности современной криптографии. В 1995 году Импальяццо написал основополагающую статью, в которой переформулировал возможные решения проблемы P и NP на языке пяти гипотетических миров, в которых мы могли бы жить, и которые получили забавные названия «Алгоритмика», «Эвристика», «Пессиленд», «Миникрипт» и «Криптомания». Пять миров Импальяццо вдохновили целое поколение исследователей и продолжают определять направление исследований в бурно развивающейся области метасложности.

КИНЕМАТОГРАФИЯ: Джесси Арагон
----------
Читайте полную статью со ссылками на статьи:
https://www.quantamagazine.org/the-re...

Читайте статью в Quanta о пяти мирах Импальяццо — в какой вычислительной вселенной мы живём?
https://www.quantamagazine.org/which-...

----------
Главы:

00:00 Криптография — убойное приложение Computational Complexity
01:31 Пять миров Импальяццо
02:03 Мир 1 — Algorithmica
02:27 Мир 2 — Heuristica
02:53 Мир 3 — Pessiland
03:15 Мир 4 — Minicrypt
03:52 Мир 5 — Cryptomania — криптография, какой мы её знаем
----------
ПОСЕТИТЕ наш сайт: https://www.quantamagazine.org
ПОДПИШИТЕСЬ на нас в Facebook:   / quantanews  
ПОДПИШИТЕСЬ на нас в Twitter:   / quantamagazine  

Quanta Magazine — независимое издание, поддерживаемое Фондом Саймонса: https://www.simonsfoundation.org/