Есть проблемы гораздо сложнее, чем NP-Complete
Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.
В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать дальше →
Источник: Хабрахабр
- Хабрахабр Информационная безопасность Блог компании Timeweb Cloud Алгоритмы Информационная безопасность Криптография Математика timeweb_статьи задача тысячелетия теоретическая информатика теория алгоритмов теория вычислимости классы сложности машин
- Настрочить жалобу в спортлото
- Albert_Wesker
- Распечатать
- TG Instant View
💬 Комментарии
В связи с новыми требованиями законодательства РФ (ФЗ-152, ФЗ «О рекламе») и ужесточением контроля со стороны РКН, мы отключили систему комментариев на сайте.
🔒 Важно Теперь мы не собираем и не храним ваши персональные данные — даже если очень захотим.
💡 Хотите обсудить материал?
Присоединяйтесь к нашему Telegram-каналу:
https://t.me/blogssmartzНажмите кнопку ниже — и вы сразу попадёте в чат с комментариями