是否可以證明NP-Complete概率不存在多項式算法？

Question

我真的無法真正瞭解它是什麼意思，說一個問題是NP完成。任何人都可以幫我解決以下問題嗎？

一個NP完全問題是一個問題，人們可以證明一個算法在多項式時間求解它不存在。這個陳述是真實的嗎？

我想說這種說法是不正確的，因爲任何人實際上證明這種算法不存在任何NP完全問題？從各種來源四處觀看，我知道對於任何NP完全問題，沒有多項式時間算法是已知的;但是，它不能被證明。

任何幫助將不勝感激。謝謝。

Answer 1

在某些情況下，有可能證明沒有比某個限制更好的算法。

例如，用於比較排序的O(n log n)已經是proven。無論我們未來有多聰明，我們都能確保沒有人會發明一種比較排序。

在這種情況下，沒有人找到證據。但這並不意味着它不能被證明。

Answer 2

該聲明更根本錯誤：有多個問題無法在多項式時間內解決，這比NP問題困難得多。 NP完全性的一個點是存在的多項式時間解，相當於P = NP（這意味着解決方案不存在意味着P！= NP）。