- 締切済み
ハミルトン閉路とNP
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
ハミルトン閉路問題が P に属することを証明できたら, 大変なことになりますよ.... 「ハミルトン閉路を持つグラフ」が本当に「ハミルトン閉路を持つ」ことを, あなたならどのように示しますか?
- Tacosan
- ベストアンサー率23% (3656/15482)
「HCがPに属することを証明すれば良いのでしょうか」というときの「HC」って何を指してますか? 「ある問題が NP に属する」ことを証明するには, 普通は「正例に対する証拠により多項式時間で検証できる」という方針を使うんじゃないかな. 「NP完全問題に帰着できる」ことを言ってもいいはずだけどなんか違和感があります.
関連するQ&A
- Ｐ≠ＮＰ問題についての質問です。
Ｐ≠ＮＰ問題についての質問です。 この問題の議論されている意味が分かったような？分からんような？、なので質問します。 大方の研究者は、「Ｐ≠ＮＰ」ではないか？、という予想をしているようですが、この問題の結論は、 (1)Ｐ＝ＮＰ (2)Ｐ≠ＮＰ のどちらかひとつ、という解釈で間違いありませんか？ また、(1)と証明された場合、「全てのＮＰ問題はＰ問題に属する。」ことを示さねばなりませんよね？現在、ＮＰ問題（例：ナップザック問題、ハミルトン閉路問題・・・）とされている、全てのものが「ＮＰ⊂Ｐ」であることを証明しないと、「Ｐ＝ＮＰ」、であることは証明されたことになりませんよね？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 一方で、(2)と証明された場合、「少なくともひとつのＮＰ問題はＰ問題に属さない。」ことを示せば大丈夫ですよね。 即ち、「何かひとつでいいから、ＮＰ問題であるけど、多項式アルゴリズムがない。」という問題を証明すればいいんですね？？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 冒頭で書いた「Ｐ≠ＮＰが有力」というのは、「ひとつでいいからＰ問題に属さないＮＰ問題を見つければ良い。（多項式時間帰着可能でない、非決定性チューリングマシンが存在する。）」という裏付けであると考えていいのでしょうか。 ど素人なので勘違いしているかもしれませんが、解説お願いいたします。
- ベストアンサー
- 数学・算数
- NPクラス、Pクラス、NP完全問題について教えてください
こんにちは。 授業でNPやPというような言葉が出てくるのですがいまいち理解できません。 あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか？ 自分なりに理解したことを書くと Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。 NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。 また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。 ご回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- ハミルトンに関する質問
点数nが３以上で、最小次数がn/2以上であるグラフGはハミルトン閉路を持つことを示したい １，Gの最長路P＝X0X1・・・・Xkを考える （X0,Xi+1)がE(G)に含まれる、(Xi,Xk)がE(G)に含まれる となるようなiが存在することを示せ ２，上記iに対して、 閉路 Xi,Xi+1,Xi+2・・・・・,Xk,Xi,Xi-1,・・・・・,X0 がハミルトン閉路であることを示せ という問題が出てしまいました 正直証明とか苦手でどうやって手を付けたらいいかわからないので教えてください！ よろしくお願いします。
- ベストアンサー
- 数学・算数
- ハミルトンについて教えて下さい！
彼氏へのプレゼントとして、ハミルトンの腕時計を買ったのはいいのですが、 ハミルトン自体の知識がまったくありません。 （デザインと金額が気に入って買ったので・・・。） どんな事でもいいので教えて下さい！
- ベストアンサー
- レディース服・下着・水着
- 未解決問題 P＝NP について
資料が英語なので、意味すら理解していません。 なぜ、P=NPが未解決問題になったのでしょうか？ P=NPが成立しないと思います。 数字を当てはめても、せいぜい P=-0 N=+0 しか思いつきません。 それから未解決問題達を解決したら、世の中ってどうなりますか？ 何か大きなメリットはあるの？
- ベストアンサー
- 数学・算数
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
- NP困難について
初めまして。NP困難について質問です。 AがNP困難とは「NPに属するどの問題もAに多項式時間で還元可能」 と定義されています。 それでNP困難について質問ですが、NP困難のクラスの問題というのは その問題がNPに含まれてるかどうかは問わず、ただ上記の定義の条件 のみで定められていると考えていいのでしょうか。つまり 「NPの問題と同程度以上に難しい問題をNP困難」 「NP困難はNPのクラスに含まれてるか、含まれてないかは問わない」 か、ということです。 また、定義「NPに含まれる問題のうちNP困難なものをNP完全」より NP困難に「NPに含まれる」という条件を加えたものが NP完全で、NP完全∈NP困難となると思います。 どこか間違ってれば指摘して下さるとありがたいです。
- 締切済み
- 数学・算数
- 【P≠NP予想】容疑者Ｘの献身を観たのですが
容疑者Ｘの献身を観たのですが、 映画の一場面で「Ｐ≠ＮＰ問題」の話題が出てきました。 その中で、 「数学の問題について、自分で考えて答えを出すのと、他人から答えを聞いて、その答えが正しいかどうかを確認するのとではどちらが易しいか（難しいか）？ ただし、その問題には必ず答えが存在する。」 というセリフがありました。 恐らく、前者がクラスＰ、後者がクラスＮＰのことを表していると思われます。 しかし、「どちらが易しいか？（難しいか？）というのは、「Ｐ≠ＮＰ問題」の本質ではないような気がします。（Ｐの方がＮＰより解くのが大変ですよね・・） Ｐ≠ＮＰ問題の核心部分は、「Ｐ⊂ＮＰが成り立つかどうか？（ＮＰ⊂Ｐは自明）」ではないでしょうか？ 自分は映画を見ていて、「そんなの、他人から答えを聞いてその答えが正しいかどうかを確認する作業の方が、自分で答えを考え出すのより何百倍も簡単だろ！！」と思ってしまいました。 詳しい方解説お願いします！！！
- ベストアンサー
- 数学・算数
お礼
すいません。HCっていうのはハミルトン閉路問題のことです。 帰着出来る事が証明出来ないのです…