Нали стана дума за седемте задачи, на които все още не е намерено решението им.
N vs NP или Проблем на Кук (формулиран през 1971г.).
Да допуснем, че се намирате в голяма компания и искате да се убедите, че там се намира Ваш познат. Ако Ви кажат, че той седи в ъгъла, то на Вас ще Ви бъде достатъчно за секунди, само с бърз поглед, да се убедите в истинността на информацията. В отсъстствие на тази информация ще Ви бъде нужно да минете през цялата стая, като преглеждате гостите.
По същия начин, ако някой Ви съобщи, че числото 13717421 би могло да се представи, като произведение на две по-малки числа, трудно бихте се убедили в истинността на информацията, но ако Ви се съобщи, че изходното число може да се разложи на множители 3607 и 3803, то това лесно се потвърждава като се провери с помощта на калкулатора.
Тези примери илюстрират общото явление: за решението на някои задачи често изразходваме повече време, от проверката за вярността на решението. Стивен Кук е формулирал проблема: може ли проверката за правилност на решенията на задачите да бъде по-дълга, от самото получаване на решенията, независимо от алгоритъма за проверка.
Този проблем се явява един от нерешените проблеми на логиката и информатиката. Неговото решение би могло да бъде революционно като промени основите на криптографията, използвана при изпращането и съхранението на данни.
Забележка: Това е мой превод и е възможно да съм допуснал грешки.
Преводът е от руски и е от сайта:
http://rc.nsu.ru/text/news/Physics/093.htmlВ момента работя по "Хипотезата на Риман" - човек като се занимава с математика как бързо си минава деня само...
