4551
правка
Задача коммивояжера с несколькими внутренними точками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача коммивояжера с несколькими внутренними точками (посмотреть исходный код)
Версия от 11:03, 25 мая 2018
, 25 мая 2018→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
На данный момент не найдено нижней границы временной сложности. В частности, возможно ли при наличии разумных теоретико-сложностных предположений доказать невозможность существования алгоритма решения задачи коммивояжера с временем выполнения | На данный момент не найдено нижней границы временной сложности. В частности, возможно ли при наличии разумных теоретико-сложностных предположений доказать невозможность существования алгоритма решения задачи коммивояжера с временем выполнения <math>2^{O(\sqrt{k})} poly(n)</math>? | ||
== См. также == | == См. также == | ||