「NP困難」の版間の差分
削除された内容 追加された内容
m robot Adding: ko:NP-난해 |
編集の要約なし |
||
1行目:
'''NP困難''' (-こんなん、NP-hard)とは[[計算複雑性理論]]におけるクラスの1つであり、問題 ''H'' がNP困難のクラスに属することは、「[[NP]]に属する任意の問題が''H''へ[[多項式時間帰着]]可能である」と定義される。
NP困難
NP困難な[[最適化問題]]は、最適解を求めるのが非常に困難であるため、[[近似アルゴリズム]]に関しても研究されている。
|