Проблема решения-проверки Кука-Левина заключается в том, что на проверку любого решения уходит меньше времени, чем на решение самой задачи. Если наглядно: мы знаем, что где-то на дне океана есть клад, но не знаем, где именно. Его поиски могут проходить поэтому бесконечно долго. Если же мы знаем, что клад находится в таком-то квадрате, определенном заданными координатами, то поиск клада существенно упростится.
И так всегда. Скорее всего. Пока что никому из математиков и простых смертных не удалось найти такую задачу, решение которой заняло бы меньше времени, чем проверка правильности её решения. Если вдруг у вас получится найти такую — срочно пишите в институт Клэя. Если комиссия математиков одобрит — миллион долларов у вас в кармане.
Проблема Кука-Левина была сформулирована ещё в 1971 году, но до сих пор никем не решена. Её решение может стать настоящей революцией в криптографии и системах шифрования, поскольку появятся «идеальные шифры», взлом которых будет фактически невозможен.
The post Проблема Кука-Левина: почему за её решение дают один миллион долларов appeared first on Русская семерка.