NP困難
【英】:NP hard
少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる.
グラフ・ネットワーク: | K-opt法 L凸関数 M凸関数 NP困難 PERT TSP多面体 クラスカル法 |
非線形計画: | 2次の最適性必要条件 2次計画問題 DC計画問題 NP困難 エラーバウンド カルーシュ・キューン・タッカー条件 カーマーカー法 |
線形計画: | 2次錐計画 NP困難 アフィン変換法 カーマーカー法 シンプレックス法 ポテンシャル関数 中心パス |
スケジューリング: | 1機械問題 3つ組み記法 FMSスケジューリング NP困難 オープンショップ問題 ガントチャート グループスケジューリング |
組合せ最適化: | 0-1整数計画 2次割当問題 AVL木 NP困難 TDI性 アルゴリズム オンラインアルゴリズム |
計算幾何: | K-d木 NP困難 TSP多面体 アレンジメント ガブリエルグラフ スケルトン スラブ法 |
NP困難
(NP hard から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/06/01 16:46 UTC 版)
NP困難(エヌピーこんなん、英: NP-hard)とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである[1]。正確にいうと、ある問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。もしもあるNP困難問題を解ける多項式時間の機械が存在すれば、それを利用すればNPに属する任意の問題を多項式時間で解くことができる。
|
- ^ B.コルテ (2012). 組合せ最適化 第2版 (理論とアルゴリズム). 丸善. ISBN 978-4621062029
「NP hard」の例文・使い方・用例・文例
- 私は認定NPO法人に寄付をしたので、寄付金控除が受けられた。
- 私は銀行員としての技術を活かしてNPOでのプロボノ活動に従事した。
- GNP では我が国は世界第 2 位で, アメリカの次だ.
- 日本の GNP はアメリカに次いで世界第 2 位だ.
- インフレの影響を加味して調整されたGNPの別形
- GNPの成長にもかかわらず,大局的に不況感のある状況
- オークンの法則という,失業率とGNPの関係に関する考え方
- 民間非営利団体(NPO)がベロタクシーを運営している。
- この民間非営利団体(NPO)は接近する小惑星や,切り離されたロケット部品などのような宇宙デブリを監視している。
- 同省は日本中の港で,個人やNPO(民間非営利団体)をそれぞれの港のサポーターに認定する予定だ。
- 静岡の民間非営利団体(NPO)が卓球を普及させようと熱心だ。
- このNPOは,卓球競技者の協会だ。
- 選挙に先立ち,民間非営利団体(NPO)「ライツ」は,10代の若者のための模擬選挙といくつかの関連イベントを企画した。
- NPOのメンバーと,13から19歳の学生5人が,いくつかの政党本部を訪れた。
- 特定非営利活動法人(NPO)のむつらぼしが,現在,笛のついた携帯電話用ストラップを作っている。
- 11月2日,日本プロ野球組織(NPB)のチームの代表らが,新チームを運営するという楽(らく)天(てん)の申し入れを承認した。
- 楽天とライブドアは,どちらもインターネットサービスの会社であり,NPBに加入しようとせり合っていた。
- それは民間非営利団体(NPO)のエコ・テクル岐阜によって開発された。
- バファローズのゼネラルマネジャーは,彼のくじにNPB(日本プロ野球組織)の印を見つけ,自分のチームが辻内選手と交渉する権利を得たと発言した。
- NPB関係者は確認せずに,バファローズが抽選に当たったと発表した。
- NP hardのページへのリンク