Есть проблемы гораздо сложнее, чем NP-Complete
Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.
В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать дальше →
Источник: Хабрахабр
Похожие новости
- ИИ Агенты как новая киберугроза: бизнесы теряют деньги и данные, не понимая почему
- Архитектура PERA для построения промышленной сети
- Telegram Web съел 30% моего 16-ядерного процессора. Расследование странного поведения, или Призрак майнера в браузере
- Настройка межсетевого SSH-доступа в многосегментной сети Cisco и MikroTik в среде GNS3
- Рост продаж на маркетплейсах без демпинга: возможен или нет
- Vitamin.tools: Как быстро и эффективно находить сотрудников или собрать пожертвования через VK Ads: два кейса от клиента Vitamin.tools
- Лебедев Денис: Боты статистики в Telegram: что они умеют, кому подходят
- От BlueBorne до LE Secure: как Bluetooth выжил после самых громких дыр
- Ты не покупатель. Ты — герой мифа
- Андрей Кружков: Как я вывел сайт в ТОП за 3 месяца без копейки: честный SEO-план на коленке