Криптография сегодня как никогда в моде. Если простыми словами, то это наука о способах безопасной передачи данных в присутствии третьих лиц. Если ещё проще, то это наука о шифровании. Сегодня, когда ЦРУ прослушивает даже президентов и канцлеров, вопрос шифрования стоит очень остро. И не только в мессенджерах. Но и в банковских переводах и платежах. Да и много где ещё. А вот эта задачка в своё время совершила переворот в теории криптографии. Попробуйте её решить и испытать катарсис первооткрывателя...

Теорема Карпа-Липтона, выдвинутая учеными Ричардом Карпом и Ричардом Липтоном, занимает центральное место в теории сложности вычислений. Она представляет собой важное звено в понимании взаимоотношений между ключевыми классами сложности, такими как NP и PH. Понятия теории сложности Для понимания теоремы Карпа-Липтона необходимо разобраться с основными терминами теории сложности. Включает задачи, для которых правильность решения можно проверить за полиномиальное время. Примеры задач NP включают различные типы оптимизаций и проверки...