正確には4色問題とはいい難いかもしれませんが、4色問題も関係なしとは言えないし、大目に見てください。実は、3彩色問題にP-NP問題が絡む疑問なのです。長くなりますが、ご容赦ください。
3彩色問題とは、御存知でしょうが、任意の地図で隣り合う国を異なる色にする条件で塗り分けるのに3色で足りるか判定せよ、という問題で、NP完全問題として知られています。
いま、ある地図が与えられ3色塗り分けが可能か判定せよ、とされたとします。そこで、ある方法、例えば、全ての2次元平面に描かれた地図は千数百か数百の基本パターンの組み合わせによって作られる(正確には不可避集合と呼ぶべきかもしれませんがここでは基本パターンとよぶことにします)ことを利用して、そのパターン群中、塗り分けに3色で足りるパターンを抽出しておき、それが与えられた地図の中にあるか検出して、3色で足りるか4色必要かを判定するとします。これには、結構な時間がかかるかもしれませんが、うまくいけば国の数=nとして、コンピュータの処理ステップ数に換算してn²∼³に比例する手間で判定でき(るかもしれず)たとすると、NP完全問題が一つ、多項式時間で解けたことになる。NP完全問題の性質として、一問でも多項式時間で解ければ、他のNP完全問題も多項式時間で解けることになり、つまりはP=NPということになります。
が、そううまくはいかないでしょう。何故か?
上記の方法で判定結果そのものは正解だったとしても、たまたま与えられた地図が多項式時間で解ける問題、つまりP問題ともいうべきか、だったから、言い換えると、3彩色問題すべてがNP完全問題とは限らず、中にはP問題もあるだろうからです。
そこで疑問は、3彩色問題で、PかNP完全かをどうやって見分ければよいのか、その方法は?ということなのです。(もしかすると、この見分け自体、NP問題なのかも?)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 『完全<困難』 2 2022/11/28 06:36
- 数学 『4色問題⓶』 3 2022/10/31 06:17
- 計算機科学 判定問題がPに属するなら探索問題はNPに属する。では判定問題がNPに属するとき探索問題は? 2 2023/05/20 19:10
- 数学 『4色問題⓵』 9 2022/10/24 06:54
- 数学 数2Bの数列の問題です。 自分は、 まず数列 an=ar^(n-1)と置き こちらの問題の、y= の 1 2022/07/07 16:26
- 統計学 統計学 二項分布の正規近似について 2 2023/02/10 11:58
- 数学 『数学的帰納法のトリセツ』 4 2022/06/06 07:34
- 数学 数学Aの組み合わせの問題で、右の図のように、正方形を各辺の中点で結んで5つの領域に分ける。隣り合った 4 2023/08/10 09:15
- Visual Basic(VBA) VBAで早押しゲームを作りたい 4 2022/05/12 13:46
- その他(職業・資格) 色彩検定1級について 2 2022/05/06 16:20
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
サンプル数の違うものの比較
-
統計における危険率
-
統計で比較するサンプル数について
-
二元配置分散分析の相互作用に...
-
二つのデータの波形が似てるか...
-
TSOのデータセット格納場所の検索
-
相関係数Rの2乗について
-
SQLの副問い合わせと相関副問い...
-
相関係数と有意差
-
線型回帰分析でy=αx+β+uとあり...
-
ある1点で傾きが急激に変化する...
-
回帰式と近似式について
-
残差について
-
分析バリデーションにおける真...
-
ケモメトリックスって何ですか?
-
切片あり回帰と切片なし回帰
-
質的データと量的データの相関...
-
メチルエステル化
-
相関の表現について(高い、強い?)
-
三つの相関係数の有意差
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
サンプル数の違うものの比較
-
統計で比較するサンプル数について
-
エクセルでANOVA
-
統計における危険率
-
ボンフェローニの補正について...
-
二元配置分散分析で主効果が見...
-
仮説の設定の仕方
-
アルゴリズムの問題
-
超準解析とイプシロンデルタ論...
-
149cmと177cmの差ってこんなも...
-
有意水準の求め方がわかりません。
-
8ミクロンって手で触ったり目で...
-
『4色問題③』
-
SPSS 多重比較ボンフェロー二...
-
測定日の異なるデータで有意差...
-
二元配置分散分析の相互作用に...
-
算数の和差算の解き方について...
-
3群間の検定について(カイ二...
-
統計の有意差について教えて下...
-
???2要因分散分析 3つの指...
おすすめ情報
些か極端な例:自転車の車輪形地図グラフ