[解決済み] コンピュータサイエンスにおけるNP完全とは何ですか？

質問

NP完全問題とは何ですか？なぜコンピュータサイエンスの重要なトピックなのですか？

どのように解くのですか？

名詞 は 非決定論的 多項式 時間です。

これは、非決定論的チューリング機械（通常のチューリング機械のようなものだが、非決定論的選択関数も含む）を用いて、この問題を多項式時間で解くことができることを意味する。基本的に、解は テスト可能 をポリタイムで表示します。もしそうで、既知のNP問題が、与えられた問題を修正した入力を使って解けるのであれば（NP問題は 縮小 を与えれば、その問題はNP完全となる。

NP完全問題は、既知の方法では多項式時間で解くことができないということが最大のポイントです。NP-Hard/NP-Completeは、ある種の問題が現実的な時間では解けないことを示す方法である。

編集部：他の方もおっしゃっていますが、NP-Completeの問題には近似解が存在することがよくあります。この場合、近似解は通常、特別な表記法を用いて近似境界を与え、その近似がどの程度近いかを教えてくれる。