Равенство классов P и NP

0 голосов
52 просмотров

Равенство классов P и NP


Математика (83 баллов) | 52 просмотров
Дан 1 ответ
0 голосов
Правильный ответ

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

А насчёт пользы, если P=NP, то любой шифр, например, можно взломать. А ещё смогут нормально просчитывать как скручиваются белки, и изобретут лекарство от рака и спида (не факт, конечно, но это не шутка)

(54 баллов)