是否有可能找到解決NP完全問題的概率？

Question

標題涵蓋了整個問題。是否有可能推導出一個函數來肯定地說，一個NP完全問題的建議解決方案有百分之一百的機會是正確的？

Answer 1

我對此表示懷疑。例如，隨機函數的最優概率是numberOfOptimalSolutions/searchSpace。所以如果你知道答案的話，你可以推導出數量最少的解決方案（這是IIRC總是比找到一個NP完全問題的最佳解決方案更難知道）。

「追求旅行推銷員」一書中列出了TSP中的每個建築啓發式在最壞的情況下與最佳解決方案的距離有多遠（或多遠）。它還提到了這些算法中（某些算法）的平均正確百分比，但IIRC可能基於抽樣，隨着問題的擴大，它會變得更糟。