Какие плюсы и минусы конструктивного доказательства P=NP (с алгоритмом)?

Question

[gghaker]

С минусами понятно - перестаёт работать шифрование и всё что от этого зависит: мобильные телефоны, спутниковое тв, онлайн игры...
А плюсы есть какие нибудь?

Answer 1

[Владимир Дубровин]

В предположении, что доказательство будет алгоритмическим, и его можно будет использовать на практике, это сделает более эффективным решение всего класса NP-полных задач, их сложность станет не экспоненциальной, а полиномиальной.
Список задач есть здесь:
https://en.wikipedia.org/wiki/List_of_NP-complete_...

На самом деле, это может и ничего не дать, т.к. в конкретной задаче с конкретными размерностями требуемый полином может оказаться менее эффективным, чем экспонента.