В математике есть одна нерешённая задача. Проблема Кука.
Стивен Кук сформулировал проблему так: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки.
Допустим, находясь в большой компании, вы хотите убедиться, что там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то вам достаточно доли секунды, чтобы, бросив взгляд, убедиться в истинности информации. В отсутствие этой информации вы будете вынуждены обойти всю комнату, рассматривая гостей. Это говорит о том, что решение какой-либо задачи часто занимает больше времени, чем проверка правильности решения.
Стивен Кук сформулировал проблему: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки. Эта проблема является одной из нерешенных проблем логики и информатики. Ее решение могло бы революционным образом изменить основы криптографии, используемой при передаче и хранении данных.
⇢