
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
研究者って「既存の概念」に対しては案外保守的だからなぁ.... もちろん私がその辺の権限を持っているわけでもないんだけど.
さておき「解(と称するもの)が提供されても、正解か確認するのにNP時間、より具体的には、指数関数時間かかる問題とする」というのはちょっと問題があるような気がするねぇ. そもそも「NP時間」ってなんだよってところから突っ込まれるし「指数関数時間かかる」の「かかる」は「高々それだけあればできる」「少なくともそれだけは必要とする」のどちらの意味にもとれてしまう. でもって「指数関数時間というのは」のところでも「コンピュータでの」はきちんと定義しないとダメだし「n∧nとかn∧n!程度」は「『程度』の意味がはっきりとしない」し「∧」をべき乗と解するなら「n^n と (n^n)! と n^(n!) はどれも全く違う」ということになってしまう.
さらに駄目出しすると, その「定義」では「NP困難」の「NP」の意味がわからなくなるんだ. 今の定義なら「NP」と「NP困難」の関係は明確だけど, その「定義」では「NP」と「NP困難」がどのように関係する?
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に含まれる、まれないに関わらず、それなりに、”困難”の性質を表していると思うのですが…。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
高1の数学でこんな感じに解の公...
-
2次不等式X^2+MX+M<0が実数...
-
2000年 大阪市立大学
-
x^2+12x+m=0において、2つの解...
-
【問題】 2次関数 f(x)=x^2−2ax...
-
n-1C2+nC2=n+2C2のとき、自然数...
-
なぜ「異なる2つの実数解」と書...
-
4XX+5X-1=0
-
解き方を。
-
「解せません」という表現
-
新スタ演かやさ理か迷っています。
-
二次方程式の解の書き方
-
2次方程式の解と係数の関係の...
-
二つの解をもち、異符号のとき
-
二つの二次方程式が共通解をもつ
-
判別式はyにおいても使えますか...
-
2次方程式x^2-x-1=0の2つの解を...
-
有理数解をもつ条件に関する問...
-
複素数と方程式の問題
-
平安神宮抽到第十番 求解
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
【問題】 2次関数 f(x)=x^2−2ax...
-
高1の数学でこんな感じに解の公...
-
なんでx軸と接しているところが...
-
2次方程式でX^2-3x+2k=0 が...
-
2次不等式X^2+MX+M<0が実数...
-
判別式はyにおいても使えますか...
-
2次方程式x^2-x-1=0の2つの解を...
-
解なしと実数解なしのちがいは...
-
なぜ「異なる2つの実数解」と書...
-
因数分解 数字を早く見つける方法
-
数が大きい式の因数分解をする...
-
異なる4つの解
-
対称行列同士の積は対称行列?
-
小学生の時(40年前)に、18÷...
-
共通解の問題についてです。こ...
-
x^2+12x+m=0において、2つの解...
-
数学の質問です
-
数学
-
わからないので教えてください(...
-
高校数学についてです。 以下の...
おすすめ情報