NP-complete
NP完全
Definition 定義
Describing a decision problem in NP to which every other problem in NP can be reduced in polynomial time; no polynomial-time algorithm is known for such problems.
Example 例文
The traveling salesman problem in its decision form is NP-complete, so heuristic methods are often used for large instances.
日本語訳を表示
判定問題としての巡回セールスマン問題はNP完全であるため、大規模な問題例にはヒューリスティック手法がよく用いられる。
Collocations よく使う組み合わせ
- ~ problem
- prove that X is ~
- NP-hard and ~
「~」の部分に NP-complete が入ります。