Равенство классов P и NP, обьясните в чём суть этой теории?

Question

А также в чём е ценность, ведь из неё по сути ничего полезного не извлечешь. ну я так думаю)

Answer 1

нет такой "теории".
есть два класса задач - класс P - задачи, которые решаются за полиномиальное время,
и класс NP - задачи, которые эквивалентны задаче коммивояжера.
 
Можно ли решить задачи NP за полиномиальное время - неизвестно.
 
В чем ценность? В том же, в чем и ценность любой математической задачи. Она дает понимание. Ну а что потом где-то на практике пригодится - никому не известно.
 
Вот недавно выяснилось, что еще Гаусс придумал быстрое преобразование Фурье, но не опубиковал за ненадобностью. Через век его снова переоткрыли - и оно стало мощнейшим инструментом, без которого трудно представить и обработку звука и изображений, и криптографию, и мобильники, и банкоматы, и mp3, и dvd.

Answer 2

Есть задачи, ответы на которые легко проверить, и понять, правильные они, или нет (например, тебе даны много чисел, и нужно выбрать 15 так, что бы их сумма была равна 100 - если у тебя есть ответ ты можешь легко проверить его правильность, сложив эти числа, и увидев получается 100 или нет)
Равенство Р и NP означает, что все задачи которые так легко можно проверить, можно решить достаточно быстро. Это то что написано выше, "полиномиальная сложность" - обычно сложность задач, таких как та, которую я привёл в пример, зависит от количества исходных элементов. Полиномиально - означает, что количество шагов в алгоритме решения прямо пропорционально количеству элементов, или их квадрату, или кубу и т. д. Это хорошо. А если они пропорциональны експоненте этого количества, это означает, что уже при тысяче элементов никто не решит такую задачу. Это плохо.
Я упрощал как мог)
 
А насчёт пользы, если P=NP, то любой шифр, например, можно взломать. А ещё смогут нормально просчитывать как скручиваются белки, и изобретут лекарство от рака и спида (не факт, конечно, но это не шутка)