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