問題がNP完全であると言うことが本当に何を意味するのか理解できないようです。誰かが次の質問で私を助けてもらえますか？
NP完全問題は、多項式時間でそれを解くためのアルゴリズムが存在しないことを証明できる問題です。その声明は本当ですか？
このようなアルゴリズムがNP完全問題に存在しないことを誰かが実際に証明できるので、このステートメントは真実ではないと言いたいと思います。さまざまな情報源を調べてみると、NP完全問題の多項式時間アルゴリズムは知られていないことがわかります。ただし、それを証明することはできません。
どんな助けでも大歓迎です。ありがとう。
状況によっては、特定の制限よりも優れたアルゴリズムが存在しないことを証明することができます。
たとえばO(n log n)、比較ソートの限界が証明されています。私たちが将来どんなに賢くなっても、誰もO(n)比較の種類を発明することは決してないだろうと確信することができます。
ただし、この場合、誰も証拠を見つけていません。しかし、それはそれが証明できないという意味ではありません。
このステートメントは根本的に間違っています。NP問題よりもはるかに難しい、多項式時間では解決できない問題があります。NP完全性のポイントは、存在する多項式時間解がP = NPと同等であることです（つまり、存在しない解はP！= NPを意味します）。