- 締切済み
クリーク問題の計算複雑度
最近計算量理論を独習する中で「クリーク問題」なるものを知りました。 <クリーク問題> 入力: グラフG、正整数k 質問: Gは大きさkのクリーク(完全グラフ)を含むか? このクリーク問題の計算複雑度はNP完全とのことです。一方 <3クリーク問題> 入力: グラフG 質問: Gは大きさ3のクリークを含むか? この3クリーク問題の計算複雑度はPとのことです。そして3に限らず(5とか100とか)任意の数の場合でやはり計算複雑度はPとのことです。(下記URL参照) ここで疑問に思ったのですが、(PとNPは同一ではないという前提で)上の二つ(クリーク問題はNP完全、3クリーク問題はP)は矛盾してはいないでしょうか。すなわち、3クリーク問題、4クリーク問題、...がPで解けるのであればクリーク問題もPで解けるのでは、ということです。 どなたかこの件を解説していただけないでしょうか。 どうぞよろしくお願いいたします。 http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/30126probs2.pdf http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/ex_2_ans.pdf
- 数学・算数
- 回答数2
- ありがとう数5
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- graphaffine
- ベストアンサー率23% (55/232)
先ほどの回答の後でよく考えてみたら、昔はクリークに関する問題で有名なものは最大クリーク問題だけでした。従って、最大クリーク問題を単にクリーク問題と言っていたような気がします。 実際、私は質問者様が挙げた形のクリーク問題は知りませんでした。 AHOの本で言っているクリーク問題とは最大クリーク問題のことのような気がします。その本を持っていないので確認できませんが。 これだけでは何なので、下のサイトから状況証拠を。 http://www.ipsj.or.jp/katsudou/sig/kaikoku/MPS42.html ここには、ある研究会の発表タイトル一覧にがありますが、その中に、以下の内容があります。 [クリーク問題と応用] （42-１１） 15:30-16:00 Title: 最大クリーク抽出アルゴリズムの実験的評価
- graphaffine
- ベストアンサー率23% (55/232)
英語は弱いので、参考のPDFはおいといて回答します。 >このクリーク問題の計算複雑度はNP完全とのことです。 ただのクリーク問題と最大クリーク問題がごっちゃにされてるような。 NP完全は後者のことでしょ。 ご質問でのクリーク問題は、3クリーク問題、4クリーク問題、..を一般化させたkクリーク問題ですよね。本質は変わらないと思います。 最大クリークは、下記参照。 http://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E3%82%AF%E3%83%AA%E3%83%BC%E3%82%AF%E5%95%8F%E9%A1%8C
お礼
どうやら以下のようなことのようです。 -------- たとえば <3クリーク問題> 入力: グラフG=(V, E) 質問: Gは大きさ3のクリークを含むか? はGの頂点数をnとしてO(n^3)で判定できる。しかし、 <クリーク問題> 入力: グラフG、正整数k 質問: Gは大きさkのクリーク(完全グラフ)を含むか? についてはcをある定数としてO(n^c)で判定できるようなアルゴリズムはまだ見つかっていない。なので現在のところクラスPに属するとは言えない。(しかし、「証明」が与えられたときにその正しさをnの多項式時間で検証できるので、クラスNPには属する) -------- 貴重なお時間を費やして考えてくださった皆様、どうもありがとうございました。
補足
御投稿ありがとうございます。 >ただのクリーク問題と最大クリーク問題がごっちゃにされてるような。 >NP完全は後者のことでしょ。 「アルゴリズムの設計と解析II」(エイホ他著、サイエンス社)という本の143,144,153ページに「クリーク問題はNP完全」とあり、ネット検索で見つかるいろいろな大学の講義資料でも「クリーク問題(kクリーク問題)はNP完全」と書かれているのですが、それらは誤りということでしょうか。 >本質は変わらないと思います。 クリーク問題(kクリーク問題)はPに属する問題ということでしょうか。 御教示どうぞよろしくお願いいたします。
関連するQ&A
- ３彩色問題について質問です。
下記の問題が解けません。説明をよろしくお願いします。 P=NPとする。３彩色可能グラフがあるとして、有効な３彩色を作れる多項時間アルゴリズムが存在することを示せ。 ヒント：P=NPの仮定はグラフが多項時間内で３彩色可能なグラフかどうかを決定できることを示唆する。しかしP=NPの仮定にはこのテストがどのようになされるかしめされていない。大事なのはそのテストが探せるということを証明することである。
- 締切済み
- 数学・算数
- ベクトル、４角形を用いた問題の計算過程が知りたいです！！
※各ベクトルの上には、“→”が省略してありあす。 ※同じような質問があったみたいですが、私のやつは、４角形なので別物。 （問い）４面体において、各、頂点をＡ，Ｂ，Ｃ，Ｏとします。 ＡＢの中点をＰ、ＢＣの中点をＱ、ＡＣの中点をＲ、ＡＯの中点をＬ、ＣＯの中点をＮ、ＢＯの中点をＭとします。 ＯＡ＝ａ、ＯＢ＝ｂ、ＯＣ＝ｃとします。 そのときに次の問題をとく。 （１）ＬＱ、ＭＲ、ＮＰをａ，ｂ，ｃを用いて表せ （２）線分ＬＱ、ＭＲ、ＮＰの中点をそれぞれ、Ｇ(1)、Ｇ(2)、Ｇ(3)とするとき、ＯＧ(1)、ＯＧ(2)、ＯＧ(3)をａ，ｂ，ｃを用いて表せ （３）ＡＧ＝2/3ＡＱ となる点Ｇを線分ＡＱ上にとるとき、ＡＧ、ＯＧをａ，ｂ，ｃを用いて表せ （１）、（３）は自力で解けたので、（２）の解説＋途中課程をお願いします。
- ベストアンサー
- 数学・算数
- 100℃の湯と0℃のをくっつけても５０℃にならないのは？
中西博士の http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1524-9.pdf ｐ５８ 熱伝導の限界 で、 100℃の湯と0℃の水を、くっつけた場合、 ＞複雑な無限級数を計算して その温度の極限値が 100℃であることを示した とあります。 どんな、無限級数なのか興味があります。 教えて頂ければ幸いです。
- ベストアンサー
- 物理学
- ＣＳ検定表計算２級ドリルについて
ＣＳ検定表計算２級を受ける予定なのですが、グラフの作成がうまくいきません。今、練習で使っている九州出版のＣＳ検定表計算2級ドリルlesson11（グラフ作成）問題8のグラフの作成の仕方がわかる方、教えてください。よろしくお願いします。
- ベストアンサー
- オフィス系ソフト
- 高校数学の問題
数学で分からない問題があるのですがどなたかお力添えを頂けると助かります。 ２次関数ｙ＝４ｘ＾２＋４ｐｘ＋３ｐ－１・・・・・(1)について考える。ただし、ｐ≠０とする。 (１)(ア)分の(イ)－√(ウ)＜ｐ＜(エ)分の(オ)＋√(カ) である。 ｐ＝１のときの(1)のグラフをＧ、ｐ＝－１のときの(1)のグラフをＴとする。 Ｇ、Ｔの共有点をAとすると、点Aの座標は((キ)分の(クケ)、(コ)分の(サ))である。 (２)(1)のグラフをx軸方向にｐ、y軸方向にｐ＾２だけ平行移動したグラフを表す２次関数は ｙ＝４ｘ＾２－(シ)ｐｘ＋ｐ＾２＋(ス)ｐ－(セ)・・・・・・(2)である。 (2)のグラフが点Aを通るときｐ＝(ソタ)である。 このとき、２次関数(2)の－５≦ｘ≦０における最大値は(チツ)、最小値は(テトナ)である。 ｘの２乗をｘ＾２と表しています。 ア～ナに入るものを書けという問題なのですが分かる方よろしくお願いします。
- 締切済み
- 数学・算数
お礼
再度の御投稿をありがとうございます。 No.1への補足で挙げました「アルゴリズムの設計と解析II」(1977年発行。元本は1974年発行)ではクリーク問題は「グラフGと整数kが与えられたとき、Gがk-クリークを含むか」という問題と定義されています。 ちなみに、1979年に発行された「Computers and Intractability」(Garey, Johonson著)という本(歴史的名著らしいですが)でもクリーク問題は「入力:グラフG=(V,E)、正整数k<=|V|; 質問:Gは大きさk以上のクリークを含むか?」と定義され、それとは別に最大クリークサイズ問題が「入力:グラフG、正整数k; 質問:G中の最大クリークの大きさは正確にkであるか?」と定義されています。 ---- ですが、昔は最大クリーク問題のことをクリーク問題と言っていたかどうかには私自身はそれほど関心がなく(すみません)、質問に書いた定義に基づいてこの問題について教えていただければと思っております。 どうぞよろしくお願いいたします。