計算問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/22 03:31 UTC 版)
最小頂点被覆問題は、与えられたグラフの最小頂点被覆を求める最適化問題である。 INSTANCE: グラフ G OUTPUT: G の頂点被覆 C の大きさ k について、最小のもの。 決定問題とする場合は、これを頂点被覆問題と呼び、次のように定式化される。 INSTANCE: グラフ G と正の整数 k QUESTION: G の頂点被覆 C で、その大きさが k 以下のものがあるか? 頂点被覆問題はNP完全問題である。カープの21のNP完全問題の1つになっており、他の問題がNP困難であることを示す手段として計算複雑性理論でよく利用される。
※この「計算問題」の解説は、「頂点被覆」の解説の一部です。
「計算問題」を含む「頂点被覆」の記事については、「頂点被覆」の概要を参照ください。
「計算問題」の例文・使い方・用例・文例
- 計算問題のページへのリンク