• 締切済み

３彩色問題について質問です。

下記の問題が解けません。説明をよろしくお願いします。 P=NPとする。３彩色可能グラフがあるとして、有効な３彩色を作れる多項時間アルゴリズムが存在することを示せ。 ヒント：P=NPの仮定はグラフが多項時間内で３彩色可能なグラフかどうかを決定できることを示唆する。しかしP=NPの仮定にはこのテストがどのようになされるかしめされていない。大事なのはそのテストが探せるということを証明することである。

みんなの回答

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

どのように考えて, どこまでわかってどこで困っている? とはいえ, ヒントの日本語もおかしいなぁ.

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

関連するQ&A

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

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

  • 計算理論についての質問です

    NP完全の問題に関して指数時間アルゴリズムがあるからといってP≠NPとはいえないのはなぜでしょうか？

  • NP完全問題、NP困難問題についての質問です。

    下記の問題が存在するとされているか、存在しないとされているか、もしくはどちらでもないかを教えてください。 どちらでもないものに対しては、簡単でいいのでなぜどちらでもないとされているのか教えて下さい。 1) 指数時間内で解けないNP完全問題 2) 指数時間内で解けないNP困難問題 3) NP内に存在するNP完全でない問題 よろしくお願いします。

  • 代数の問題です。

    代数の問題です。 p=素数 Ｆ_p={0,1,2,・・,p-1} とする。 Ｆ_p上において４次の既約多項式が存在する事を証明せよ。 という問題です。 わかる方いましたらよろしくお願いいたします <(_ _)> そして、 出来ればＦ_p上においてn次の既約多項式が存在する事を証明できる方いましたら教えて頂けると助かります。

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

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

  • 「言語がNPに属するならば、非決定性多項式TMで判定可能」

    「言語がNPに属するならば、非決定性多項式TMで判定可能」 であることの証明について教えてください。 宜しくお願いします。

  • グラフ理論の問題について

    Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。

  • 【グラフ理論】証明問題が分かりません。【難問】

    テストに向けてグラフ理論の勉強をしているのですが・・・ 下記の証明問題で行き詰まってしまいました。 『uv ∉ E(G) → uw ∉ E(G)というグラフは完全K部グラフしか存在しない事を証明せよ。』 当方、証明問題に滅法弱く、どう解けば良いのか方針すら分かりません。 方針や証明の過程など詳しくご教授して頂ければ幸いです。 何卒宜しくお願い致します。

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

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

  • グラフ理論

    Gを頂点数ｎ、変数ｍの単純グラフとし、PG(k)をGの彩色多項式をし、PG(k)のk^n-1の係数が－ｍであることを示せ。 という証明問題なんですが、なんで－ｍになるのかがわかりません。 すみませんが教えてください。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する