是否正在生成所有字符串排列 NP Complete？
Is generating all strings permutation NP Complete?
计算给定字符串的所有字符串排列可以通过尝试所有可能性在 O(n!) 中解决。
现在，看看旅行推销员问题，我们可以通过尝试所有城市排列来解决它。假设我们有城市 A、B 和 C。
假设我们从城市 A 开始。通过计算 BC 字符串的所有排列，我们得到 ABC ACB，然后我们只需求和（在多项式时间内，第一种情况下 AB、CB 和 CA 之间的距离...）
所以这不是旅行推销员问题的所有字符串排列的归约，它不是 NP 完全问题吗？
我认为您混淆了一些概念：
你描述的不是"reducing the all permutations problem to TSP"，而是相反：将TSP减少到所有排列问题。
这证明了生成所有排列是 NP-Hard（至少和最难的 NP 问题一样难）。
要证明某事是 NP-Complete，您还必须证明它是 NP-Complete。但事实并非如此，一目了然：NP 是一组决策问题，您描述的问题不是决策问题。
另请参阅：What are the differences between NP, NP-Complete and NP-Hard?
计算给定字符串的所有字符串排列可以通过尝试所有可能性在 O(n!) 中解决。
现在，看看旅行推销员问题，我们可以通过尝试所有城市排列来解决它。假设我们有城市 A、B 和 C。 假设我们从城市 A 开始。通过计算 BC 字符串的所有排列，我们得到 ABC ACB，然后我们只需求和（在多项式时间内，第一种情况下 AB、CB 和 CA 之间的距离...）
所以这不是旅行推销员问题的所有字符串排列的归约，它不是 NP 完全问题吗？
我认为您混淆了一些概念：
你描述的不是"reducing the all permutations problem to TSP"，而是相反：将TSP减少到所有排列问题。 这证明了生成所有排列是 NP-Hard（至少和最难的 NP 问题一样难）。
要证明某事是 NP-Complete，您还必须证明它是 NP-Complete。但事实并非如此，一目了然：NP 是一组决策问题，您描述的问题不是决策问题。
另请参阅：What are the differences between NP, NP-Complete and NP-Hard?