|
В чём же "Проблема Кука"?
Во многих местах Проблема Кука формулируется так:
" Может ли проверка правильности решения задачи быть более длительной,
чем само получение решения, независимо от алгоритма?"
Конечно может. А в чём проблема?
Художник Богданов-Бельский на своей картине "Устный счёт" изобразил учеников церковно-приходской школы, вычисляющих в уме значение выражения (10^2+11^2+12^2+13^2+14^2)/365.
Моё решение.
1. Из того, что это устный счёт да ещё и в ЦПШ, можно предположить, что в ответе будет целое число.
2. Величина числителя заведомо больше 365=365х1 и заведомо меньше 1095=365х3.
Следовательно, ответ - 2.
Время решения - менее 5-и секунд.
Очевидно, что ЛЮБАЯ ПРОВЕРКА потребует БОЛЬШЕ ВРЕМЕНИ. чем 5 секунд.
Могу привести и другие примеры.
Так в чём же проблема Кука?
|
