Проблемы НП могут быть решены в детерминистически-экспоненциальное время?

Question

Любая проблема в NP может быть решена за детерминированное экспоненциальное время, или мы можем сказать, что любой язык в NP может быть решен с помощью алгоритма, работающего за время 2^O(n^k), т. е. NP ⊆ EXP

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

Тем не менее, есть простой пример, который я не могу понять, что не так с идеей, которую я сделал

Вот..

Задача коммивояжера: задан неориентированный граф G=(V,E) V=|n|

Это хорошо известная NP-полная проблема, поэтому действительно принадлежит NP

И я пытаюсь проанализировать время работы.. вот так:

Я просто перечисляю все возможные решения, и есть (n-1)! Всего возможных туров

Затем я проверяю каждый из них, для каждого возможного тура требуется O(n)

Общее время работы будет O(n!)

Это не похоже, может быть ограничено сверху 2^O(n^k), т. Е. Экспоненциальное время

где подводный камень этого анализа?

или, другими словами, как мы можем объяснить, что проблема коммивояжера действительно может быть решена алгоритмом, работающим во времени 2^O(n^k)

Answer 1

Обратите внимание, что

п! ≤ nⁿ = (2^{log n})ⁿ = 2^{n log n} ≤ 2ⁿ²

Так что! = 2^{O (n2)}, значит, n! ∈ EXP.

Надеюсь это поможет!