eleday

Есть задачи, где проверить готовый ответ можно за секунду, а найти его с нуля — практически нереально Например, представим очень сложную головоломку. Если тебе уже дали решение — ты просто подставляешь его и быстро проверяешь, что все условия выполняются А вот найти это решение самостоятельно может потребовать перебрать огромное количество вариантов И тут появляется один из самых известных вопросов информатики: P = NP? P — задачи, которые компьютер умеет быстро решать NP — задачи, для которых компьютер умеет быстро проверить уже готовое решение Вопрос звучит так: если решение можно быстро проверить, можно ли его всегда так же быстро найти? Сейчас мы этого не знаем. Возможно, существуют быстрые алгоритмы для огромного множества задач, просто человечество их ещё не придумало, а возможно, некоторых быстрых алгоритмов не существует в принципе Если вдруг окажется, что P = NP, последствия будут огромными Можно будет намного эффективнее решать задачи оптимизации, строить расписания, искать маршруты, решать сложные логические задачи Но одновременно могут возникнуть очень серьёзные проблемы с криптографией: многие системы безопасности опираются именно на то, что некоторые задачи чрезвычайно трудно решить, даже если правильный ответ легко проверить Самое забавное — вопрос сформулирован очень просто, а ответа на него до сих пор нет За доказательство P = NP или P ≠ NP Институт Клэя обещает $1 000 000 @eleday