生成所有字符串排列NP完成？

通過嘗試所有可能性，可以在O（n！）中計算給定字符串的所有字符串置換。生成所有字符串排列NP完成？

現在，看看旅行商問題，我們可以通過嘗試所有城市排列來解決它。假設我們有城市A，B和C. 假設我們從城市A開始。通過計算BC字符串的所有排列，我們得到ABC ACB，然後我們只求和（在多項式時間內，AB，CB和CA之間的距離爲第一種情況...）

因此，這不是所有字符串排列的旅行商問題的減少，並不是一個NP完整的問題？

來源

2017-07-27 fredcrs

我想你混淆了一些概念：

你描述的不是「降低所有排列問題TSP」，而是相反：減少TSP的所有排列問題。事實證明，生成所有排列是NP-Hard（至少與最困難的NP問題一樣困難）。

要證明某件事是NP完全的，你還必須證明它是在NP中。但事實並非如此，沒有道理：NP是一組決策問題，你描述的問題不是決策問題。

參見：What are the differences between NP, NP-Complete and NP-Hard?

來源

2017-07-27 15:16:42 Loonquawl

可以NP完全和NP難使用指數只解決方案來解決？或複雜性與複雜性類別無關？ – fredcrs

我的意思是......據我們所知，NP Complete和NP Hard只能用指數型複雜度算法求解，對嗎？ – fredcrs

恩，對於NP完整，是的，「據我們所知」。更確切地說： 1.我們知道NP包含EXPTIME，所以它的所有問題都可以用指數時間複雜度來解決。 2.嚴格地說，我們不知道我們不能解決所有NP問題，比如多項式時間（也就是說我們沒有證據）。這是着名的P = NP/P≠NP問題。但人們普遍認爲情況就是如此。 https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP – Loonquawl

生成所有字符串排列NP完成？

回答

相關問題