|
Главная » 2011 » Апрель » 22
- Проблема Кука (сформулирована в 1971 году)
Допустим, что вы, находясь в большой компании, хотите убедиться, что
там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то
достаточно будет доли секунды, чтобы, бросив взгляд, убедиться в
истинности информации. В отсутствие этой информации вы будете вынуждены
обойти всю комнату, рассматривая гостей. Это говорит о том, что решение
какой-либо задачи часто занимает больше времени, чем проверка
правильности решения. Стивен Кук сформулировал проблему: может ли проверка правильности
решения задачи быть более длительной, чем само получение решения,
независимо от алгоритма проверки. Эта проблема также является одной из
нерешенных задач из области логики и информатики. Ее решение могло бы
революционным образом изменить основы криптографии, используемой при
передаче и хранении данны
...
Читать дальше »
|
|
|
|