NP完全問題と計算困難性とは？

NP完全問題と計算困難性とは、解の検証は多項式時間でできるが、解を求める効率的な方法が知られていない問題群がNPで、その中で最も難しい一群がNP完全。応用情報では、厳密解を諦めて近似解法へ切り替える判断の根拠として問われる。

えぬぴーかんぜんもんだいとけいさんこんなんせい

応用情報技術者試験の頻出用語／テクノロジ系

NP完全問題と計算困難性の意味

解の検証は多項式時間でできるが、解を求める効率的な方法が知られていない問題群がNPで、その中で最も難しい一群がNP完全。応用情報では、厳密解を諦めて近似解法へ切り替える判断の根拠として問われる。

巡回セールスマン問題、ナップサック問題、多くのスケジューリング問題がこれに当たる。訪問先20か所の配送計画でも全探索はn!に膨れて破綻するため、遺伝的アルゴリズムや局所探索を使い、実用時間内に十分よい解を得る。

「NP完全＝解けない」ではない。小規模なら厳密に解けるし、解の検証は高速にできる。P≠NPは未証明の予想なので「証明済み」とする選択肢は誤り。近似解法が最適性を保証しない点も押さえる。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。