• 締切済み

NP困難について

初めまして。NP困難について質問です。 AがNP困難とは「NPに属するどの問題もAに多項式時間で還元可能」 と定義されています。 それでNP困難について質問ですが、NP困難のクラスの問題というのは その問題がNPに含まれてるかどうかは問わず、ただ上記の定義の条件 のみで定められていると考えていいのでしょうか。つまり 「NPの問題と同程度以上に難しい問題をNP困難」 「NP困難はNPのクラスに含まれてるか、含まれてないかは問わない」 か、ということです。 また、定義「NPに含まれる問題のうちNP困難なものをNP完全」より NP困難に「NPに含まれる」という条件を加えたものが NP完全で、NP完全∈NP困難となると思います。 どこか間違ってれば指摘して下さるとありがたいです。

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

単なるミスだと思いますが, 「NP完全∈NP困難」じゃなくって「NP完全⊂NP困難」ですね. それ以外は全部 OK. coNP完全な問題は NP困難だけど (P ≠ NP の仮定のもとで) NP には含まれません.

moogle0517
質問者

お礼

考えに自信がもてました。ありがとうございました。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • NP完全問題についての

    NP完全問題についての質問です （1）NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか、 　　問題のサイズをｎとしたとき「ｎの階乗」，「２のｎ乗」オーダーとなる問題は 　　NP完全問題のうちには入らない？ （2）PSPACE完全問題とは何か（NP完全問題はPSPACE問題に含まれる（？）） 以上です．よろしくお願いします．

  • 巡回セールスマン問題: NPについて

    　NP問題である巡回セールスマン問題について質問です． 　NP問題には，「非決定性チューリングマシンによって多項式時間で解くことができる決定問題」「証拠が与えられれば，その答えがYesであることを(問題の入力サイズに関する)多項式時間以内に確認することができる決定問題」などの定義があります．このふたつめの定義について質問です． 　巡回セールス問題における解を確かめる「証拠」とはいったいどのようなものなのでしょうか?

  • NPクラス、Pクラス、NP完全問題について教えてください

    こんにちは。 授業でNPやPというような言葉が出てくるのですがいまいち理解できません。 あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか？ 自分なりに理解したことを書くと Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。 NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。 また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。 ご回答よろしくお願いします。

  • 多項式時間変換

    初めまして。多項式時間還元について質問させて下さい。 問題Aが問題Bに多項式時間還元できるかの証明として (1)問題Aの任意の問題例xを多項式時間で問題Bの問題例に変換しているか. yes:解がある. no:解がない.として (2)問題Bがyes(no)ならば問題Aもyes(no). (3)問題Aがyes(no)ならば問題Bもyes(no). この(1)(2)(解の一致)と(3)(多項式時間で還元か)が必要だと思います. また,「還元できるならBはAと同程度に言える」とされています. ここで２つ質問があるのですが １つめはAがno(解がない)ならBもno,BがnoならAもnoの証明 から多項式還元可能が言えたとして「Bが解けないなら,Aも解けてない」なら問題の難しさ 比較ができなくて,同程度に難しいが言えないと思うのですがどうなのでしょうか. ２つめは,証明(2)(3)の事で.「Bが解ければAは自動で解ける.」と還元の性質より 証明(2)で矛盾を確かめているのはわかります. しかし(3)の方は何を確かめたくてしているのかわからないので教えてください.

  • co-NPについて

    計算の複雑性理論について勉強しているのですが、ある問題がクラスco-NPに属すことがわかったんのですが、そもそもco-NPに属する問題はどの程度複雑といえるのでしょうか？お願いします。

  • Ｐ≠ＮＰ問題についての質問です。

    Ｐ≠ＮＰ問題についての質問です。 この問題の議論されている意味が分かったような？分からんような？、なので質問します。 大方の研究者は、「Ｐ≠ＮＰ」ではないか？、という予想をしているようですが、この問題の結論は、 (1)Ｐ＝ＮＰ (2)Ｐ≠ＮＰ のどちらかひとつ、という解釈で間違いありませんか？ また、(1)と証明された場合、「全てのＮＰ問題はＰ問題に属する。」ことを示さねばなりませんよね？現在、ＮＰ問題（例：ナップザック問題、ハミルトン閉路問題・・・）とされている、全てのものが「ＮＰ⊂Ｐ」であることを証明しないと、「Ｐ＝ＮＰ」、であることは証明されたことになりませんよね？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 一方で、(2)と証明された場合、「少なくともひとつのＮＰ問題はＰ問題に属さない。」ことを示せば大丈夫ですよね。 即ち、「何かひとつでいいから、ＮＰ問題であるけど、多項式アルゴリズムがない。」という問題を証明すればいいんですね？？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 冒頭で書いた「Ｐ≠ＮＰが有力」というのは、「ひとつでいいからＰ問題に属さないＮＰ問題を見つければ良い。（多項式時間帰着可能でない、非決定性チューリングマシンが存在する。）」という裏付けであると考えていいのでしょうか。 ど素人なので勘違いしているかもしれませんが、解説お願いいたします。

  • 計算量(PやNP)について

    ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数)あり、深さX(未知、変数)に答えがある場合、計算量は N^X(NのX乗) になると思います。 N^Xは計算量のクラス(NP困難やNP完全等)でいうと何に属するのでしょうか？

  • この問題はNP?(円周率πの10進展開中に3がx個連続して現れるか?)

    以下のような判定問題があります。 <円周率中の3の連続出現> 入力: 正整数x 質問: 円周率を10進で展開した無限数列(3.14159...)に数字3がx個連続して並ぶ箇所があるか? この問題はクラスNPに属するのでしょうか? たとえば「証明」が与えられたとき、その正しさを入力サイズ(この場合はx?)の多項式時間で検証できればNPに属するわけですが、 この場合の「証明」とは円周率中の3がx個並んだ箇所を「ほら、i桁目からj(=i+x-1)桁目に3がx個並んでいるよ」と円周率を小数点以下j桁目まで書いて示すことなのか? ↓ そうだとしたら、その検証は円周率をj桁目まで適当な方法で計算することなのか? ↓ そうだとしたら、xの多項式時間で円周率をj桁目まで計算出来るか? ↓ 計算コストはxとは独立なのでは? などと考えるうちに分からなくなってしまいました。 どうぞよろしくお願いいたします。

  • 多項式で近似

    問題で 「x（範囲はaからb）で定義されている関数f(x)を多項式C0-C1xで近似する方法を述べよ」 というのがあるのですが、条件が少なく良く分かりません。。。 多項式近似ということで最小二乗法などで直線に近似するのかな、と考えているんですが。。。 なにか良い方法があったら教えていただきたいと思います。 よろしくお願いします。

  • 脳と量子コンピュータ

    NP問題を多項式時間で「直感的に」解けてしまう人がいたとします。 その場合、人間の脳は、量子コンピュータだと言えるでしょうか？ また、そういう実例というのは存在するでしょうか？ 私は、インドに「素因数分解を瞬時にする双子」がいるとかいううわさを 耳にしたことがありますが、出典は分かりません。 ※1　量子コンピュータの定義は適当にしてくださって結構です。 明らかに間違った定義は困ってしまいますけど＾＾； ※2　カテ違いのような気がしますが、 「NP問題」の説明にあまり自信がなかったので、 「数学」にしてみました。 ※3　回答者同士の議論、まったくもってかまいません。 もちろん、中傷・誹謗などは禁止です。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する