Проблема решения – проверка решения задачи Кука-Левина – заключается в том, что проверка любого решения занимает меньше времени, чем само решение задачи. Если ясно: мы знаем, что где-то на дне океана есть сокровище, но точно не знаем, где оно находится. Следовательно, его поиски могут продолжаться бесконечно. Если мы знаем, что сокровище находится в определённом квадрате, определяемом заданными координатами, поиск сокровища значительно упростится.
И так всегда и бывает. Скорее всего. До сих пор ни один из математиков и обычных людей не смог найти задачу, решение которой заняло бы меньше времени, чем проверка корректности её решения. Если вдруг найдёте такую ​​– срочно напишите в Институт Клэя. Если Комиссия математиков одобрит, у вас в кармане миллион долларов.
Проблема Кука-Левина была сформулирована в 1971 году, но до сих пор никем не решена. Это решение могло бы стать настоящей революцией в криптографии и системах шифрования, поскольку появились бы «идеальные шифры», которые было бы практически невозможно взломать.
Есмира Шукурова
TEREF