A 回答 (2件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
ひらたくいうと
・NP困難: NP のどんな問題より難しい (簡単でない) 問題
・NP完全: NP のどんな問題より難しい (簡単でない) NP 問題
というイメージなので, NP完全などの問題も NP に属するんだけど NP困難な問題は NP に属するとは限らない (NP よりもっと難しいかもしれない).
本来「NP」は決定問題の集合なので「NP完全」というのは決定問題のみなんだけど, 決定問題でなくても「本質的に決定問題と同程度に難しい」問題もある. なので, 「NP完全」というときに決定問題以外のものを含むこともある.
ありがとうございます。NP困難の中にはNPに含まれない問題もあるということですね。そこで改めてNP困難の定義として、ここに記した、「解(と称するもの)が提供されても、正解か確認するのにNP時間、より具体的には、指数関数時間かかる問題とする」のはどうでしょう?ここで、指数関数時間というのは、例えばTSP で、都市数=nとしたときコンピュータでのステップ数にして、n∧nとかn∧n!程度かかるという意味です。この定義だと、NPに含まれる、まれないに関わらず、それなりに、”困難”の性質を表していると思うのですが…。
No.2
- 回答日時:
研究者って「既存の概念」に対しては案外保守的だからなぁ.... もちろん私がその辺の権限を持っているわけでもないんだけど.
さておき「解(と称するもの)が提供されても、正解か確認するのにNP時間、より具体的には、指数関数時間かかる問題とする」というのはちょっと問題があるような気がするねぇ. そもそも「NP時間」ってなんだよってところから突っ込まれるし「指数関数時間かかる」の「かかる」は「高々それだけあればできる」「少なくともそれだけは必要とする」のどちらの意味にもとれてしまう. でもって「指数関数時間というのは」のところでも「コンピュータでの」はきちんと定義しないとダメだし「n∧nとかn∧n!程度」は「『程度』の意味がはっきりとしない」し「∧」をべき乗と解するなら「n^n と (n^n)! と n^(n!) はどれも全く違う」ということになってしまう.
さらに駄目出しすると, その「定義」では「NP困難」の「NP」の意味がわからなくなるんだ. 今の定義なら「NP」と「NP困難」の関係は明確だけど, その「定義」では「NP」と「NP困難」がどのように関係する?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 『4色問題③』 2 2022/11/14 00:31
- 計算機科学 判定問題がPに属するなら探索問題はNPに属する。では判定問題がNPに属するとき探索問題は? 2 2023/05/20 19:10
- 数学 『4色問題⓶』 3 2022/10/31 06:17
- 統計学 統計学 二項分布の正規近似について 2 2023/02/10 11:58
- 転職 転職の時、SPIテストの対策はどれくらい完璧にしましたか? 私は今アラサーなのですが、 ・英語系…中 2 2023/08/25 16:58
- 数学 数2Bの数列の問題です。 自分は、 まず数列 an=ar^(n-1)と置き こちらの問題の、y= の 1 2022/07/07 16:26
- 高校受験 数学の問題いくつか捨てても大丈夫?残り1ヶ月、点数が取れない教科ばっか勉強しても大丈夫? 高校受験 2 2023/01/07 17:55
- 発達障害・ダウン症・自閉症 中学の時にIQ82の境界知能と診断されました。 今の私も、やはり境界知能でしょうか? そしてこれは、 3 2023/02/19 00:37
- 高校 数学の成績の波が激しい&思い込みが強すぎるのを治したいです 6 2022/12/21 21:44
- 中学校 中学生です。 高校入試の数学の問題って、賢い大学生にとっても難しいんですか? 私が通ってる塾に大学生 7 2023/06/29 23:04
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
【数Ⅰ】次の2次方程式が重解を...
-
「解せません」という表現
-
二次方程式の虚数解と複素数の...
-
数II、解と係数の問題
-
なぜ「異なる2つの実数解」と書...
-
共通解の問題についてです。こ...
-
求伏見稻荷大社和難波八阪神社...
-
2000年 大阪市立大学
-
Z^3(Zの3乗)=-8 の複素数解...
-
2次方程式でX^2-3x+2k=0 が...
-
異なる4つの解
-
3次と2次の方程式の共通解
-
D<0はすべての実数じゃないんで...
-
高1の数学でこんな感じに解の公...
-
数学の問題集から問題をとって...
-
因数分解 数字を早く見つける方法
-
八阪神社 戀愛籤 解籤
-
日本冰川神社解籤
-
写真の数学の質問です。 なぜ、...
-
数学2の解と係数との関係につい...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
高1の数学でこんな感じに解の公...
-
3次と2次の方程式の共通解
-
求伏見稻荷大社和難波八阪神社...
-
xについての2次方程式x²-2mx+2m...
-
共通解の問題についてです。こ...
-
異なる4つの解
-
数学についてです。 aX²+bX+c...
-
数学I
-
a又はb及びc
-
対称行列同士の積は対称行列?
-
数学を教えてください。
-
二次方程式の解の書き方
-
なんでx軸と接しているところが...
-
2次・3次方程式の共通解に関...
-
なぜ「異なる2つの実数解」と書...
-
2次方程式でX^2-3x+2k=0 が...
-
数2の問題について
-
【数Ⅰ】次の2次方程式が重解を...
-
高校数学についてです。 以下の...
-
因数分解 数字を早く見つける方法
おすすめ情報