@gghaker

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы