NP完全問題と計算困難性とは？えぬぴーかんぜんもんだいとけいさんこんなんせい
NP完全問題と計算困難性とは、解の検証は多項式時間でできるが、解を求める効率的な方法が知られていない問題群がNPで、その中で最も難しい一群がNP完全。応用情報では、厳密解を諦めて近似解法へ切り替える判断の根拠として問われる。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →具体例
巡回セールスマン問題、ナップサック問題、多くのスケジューリング問題がこれに当たる。訪問先20か所の配送計画でも全探索はn!に膨れて破綻するため、遺伝的アルゴリズムや局所探索を使い、実用時間内に十分よい解を得る。
試験での引っ掛け
「NP完全＝解けない」ではない。小規模なら厳密に解けるし、解の検証は高速にできる。P≠NPは未証明の予想なので「証明済み」とする選択肢は誤り。近似解法が最適性を保証しない点も押さえる。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。