Стивен Кук сформулировал проблему: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки. Эта проблема является одной из нерешенных задач из области логики и информатики.
Из условия проблемы следует, что можно оперировать только понятиями времени и логики.
Примечание :). Вообще-то в школе учили, что задача считается решенной, если решение подтверждается проверкой. Из этой формулировки следует, что время решения задачи содержит время проверки, и, следовательно, время проверки всегда меньше времени решения задачи или они равны 0 если нет разумных существ, ставящих задачи.
Решение:
Решение Проблемы Кука поясняет рисунок, где Т-вектор времени:
Допустим в момент времени t2 сформулирована задача, и она решается до момента времени t3 завершения решения задачи. С этого момента начинается проверка решения задачи до момента времени t4 завершения проверки.
Вариант 1.
Существуют важные факторы:
--
Постановка задачи и решение задачи возможны при существовании и использовании некоторого объема информации, необходимой и достаточной для этого. Минимальный объем информации для постановки и решения задач содержит письменность и исчисление. Пока нет другого способа для постановки задач, для поиска решений и демонстрации решений. Следовательно, решение всех возможных задач было начато в момент времени t1. Если точнее, решение задач было начато при выработке письменности и счета, в момент подготовки взаимодействия двух и более разумных существ, с целью накопления, анализа и переработки информации, которая сохранилась и использована в постановке и решении конкретной задачи, а не в момент времени t2 постановки задачи. Эти разумные существа могут не встречаться, могут жить в разные интервалы времени.
--
Проверка решения задачи ограничена временем жизни проверяющего, а решение задачи нет.
Очевидно, что в варианте человеческой и подобных цивилизаций, существование этих факторов приводит к тому, что проверка правильности решения задачи не может быть более длительной, чем само получение решения, независимо от алгоритма проверки.
Вариант 2. Гипотетический - разумные существа бессмертны. Не трудно понять, что и в этом случае проверка правильности решения задачи не может быть более длительной, чем само получение решения, независимо от алгоритма проверки т.к. фактор 1 сохраняется.
