P= NPと仮定すると、多項式の時間のグラフ色の問題がどのように解決されるのでしょうか。
https://cs.stackexchange.com/questions/121710
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
$ \ sf p= np $ を持っていると仮定して、多項式時刻のグラフ色の問題を解決する方法は？
グラフ $ g=（v、e）$ 、有効な着色 $ \ chi（g）：v \ to \ {1,2、\ cdots、k \} $ は $ k $ $（u、v）\ in $ は $ \ chi（u）\nne \ chi（v）$ を意味します。"Colors"の最も少ない番号 $ k $ を最小限に抑えます。
解決
2つのケースがあります：
-
$ P= NP $ 以外：これは、したがって、除外された中央の法則によって $ p= np $ であると結論付けることができます。この場合、多項式時刻にグラフの着色を解決するためのアルゴリズム、またはその他の問題を解決するためのアルゴリズムがではありません。私たちはそれが存在しないならば、私たちは矛盾を引き出すことができることを私たちは知っています。だからこの形の証明は、迅速に問題を解決するためにかなり役に立たない。
-
$ p= np $ 建設的に。この場合、いくつかの $ np $ --hard問題のための多項式時間アルゴリズムがあります。 $ l $ 。 $ l $ がNP-HARDである場合、それは多項式時刻の他のNPハード問題を解決する必要があります（すなわち、それはその問題から減少します）。その問題は、次に、別の問題から減少するか、 $ NP $ のすべての問題から直接減少します。直接証明（おそらく3SAT）を持つものになるまで、私たちは削減の跡を追跡し続けます。
これらの削減を構成することで、多項式時刻の3SATを解くアルゴリズムを取得します（各縮小は、以前のアルゴリズムへの多項式の呼び出しのみ、および $のための開始アルゴリズムのみを行うため） L $ は多項式時刻で実行されます。
他のヒント
P= NPの場合、それはNPでは任意の問題があることを意味します。たとえば、問題は $ g $ $ k $ - colourable？"、 $ G $ は有限のグラフと $ kです。 $ 整数、多項式時間でそれを解決するためのアルゴリズムがあります。
残念ながら、私たちの問題はNPにはありません。 $ k $ - -colouringを見つけたい $ k $ 。これで、 $ k= 1の上記の問題を繰り返し解くだけで、多項式の最小 $ k $ を見つけることができます。 2、\ ldots $ は、答え "yes"を返すまで。 （注これは、 $ k $ が到達すると、以前ではない場合は頂点数が到達しますので、多項式のインスタンスのみが必要です。）
しかし、 $ k $ を知っているので、 $ k $ - -colouringを見つける方法？さて、 $ k $ が頂点数に等しい場合は、それが簡単です。すべての頂点には色が異なる必要があります。 $ k $ が頂点数より少ない場合は、任意の色付け（そして私たちが存在することがわかっている）で、2つの頂点 $ x $ と $ y $ の同じ色の（隣接していなければならない）。つまり、 $ x $ と $ y $ を組み合わせることができることを意味します（それらを削除して新しいものと置き換える $ x $ または $ y $ のすべての隣接に隣接する頂点、および同じ色の作品この新しいグラフのために。したがって、この新しいグラフは $ k $ - カラーマルバブルで、頂点が1つずつあります。
だから私たちができることは、隣接していない頂点以外のすべてのペアを介して実行されます。 $ x、y $ のすべてのペアを実行し、 $ x $ と $ Y $ は $ k $ です - 答えを得るまで、「はい」（これは最終的には起こりなければなりません）。その後、このプロセスを繰り返して、グラフのみが visticesのみを持つまで、現在の頂点を組み合わせて各現在の頂点を形成しています。これにより、元のグラフの頂点を $ k $ セットに分割し、 $ k $ - $ g $ のカラーリング。
p= npと仮定して、次のようにスケッチアルゴリズムが、多項式時に存在する場合は、入力グラフの3色付けを見つけます。ただし、そのような3つの着色がない場合は、決して終了しません。
最初に、すべての可能なアルゴリズム（チューリングマシン）を列挙し、任意の入力でのそのようなチューリングマシンの計算をシミュレートすることを学びます。
次に、接続されたポリ時タイム目覚まし時計ですべての可能なアルゴリズムを列挙することを学びます。 （これは、概念的に2つのことを並行して行うのに特別なケースを列挙していることを意味します。1セットのテープでは、「プライマリ問題」を計算し、別のテープで、固定からゼロまでカウントダウンするだけです。関数n、2 * n ^ 2,3 * n ^ 3、...、ここで、nは一次問題への入力の長さであり、これがこれに一度計算を停止します（おそらく一次問題の観点から早く）。 Primary Tape（Alarm Clockと呼ばれる）のカウントダウンは、プライマリの問題が解決される前にゼロになります。そのため、出力がプライマリの問題に対して出力されているため、計算は終了することがあります。それが起こるものは何でもするテープ。）
添付多項式目覚まし時計を持つチューリングマシンが列挙される正確な順序は網羅的なものであるべきです。上記のものの間で、チューリングマシンと目覚まし時計機能の組み合わせに遭遇するようなものであるべきです。後で。
今は、これらすべてのチューリングマシンを並列に並列に並列にシミュレートして、1つずつわずかに離間している。特に、全走行時間の半分の半分の半分が列挙で多項式目覚まし時計を備えた最初のチューリングマシンに存在することを確認してください。 3番目の機械など。 （列挙体の各チューリングマシンが、少なくとも最初の遷移まで実行し続けると仮定して、全実行時の既知の定数分数範囲を得ることを確認しています。）
どうすればいいの？例：最初のマシンの1つの移行をシミュレートします。それから再び同じもの - 最初の機械のもう1つの遷移。それから2番目の機械の1つの移行。これを再びこのすべてより：もう1つのマシンともう1つのマシンのもう1つの遷移。その後、4番目のマシンの最初の移行をシミュレートする前に、3番目のマシンの最初の遷移を行い、その後に（合計7つの遷移）の後に（合計7つの遷移）を実行します。
時々、マシンはその目覚まし時計またはその主な問題を解決したためにそれを終端します（これは、入力グラフの3つの着色の生産、誰が気にするのはめったにできません）。マシンが終了した場合は、出力テープ上の入力グラフの有効な3色付けが発生したかどうかを確認します。そうすれば、アラームクロックが接続されているすべてのチューリングマシンのシミュレーション全体を終了し、出力。
正直に言うと、私はマシンからマシンへの注意を切り替えることのオーバーヘッド、機械を繰り返すことのオーバーヘッド（つまり、列挙体の初期状態の生成）のオーバーヘッドを充電することができることを密接にチェックしていません。 ）端末状態を確認することのオーバーヘッド（有効な3の着色時に終端機がつまずいたかどうか）。しかし、私は確かに個々のチューリングマシンのシミュレートされた遷移にもっと多くの時間を費やして、すなわち、全オーバーヘッドが100％未満の一定の要因である。
今、3色の問題の機能版がその決定版に自己還元可能であることはよく知られています。決定問題のための単純な多項式時間アルゴリズムが（P= NPだけ）、したがって、存在するときはいつでも多項式の色調で実際に実際に3つの色調を確実に識別する自己減少アルゴリズムが発生し、 すべてのチューリングマシンのうち、リベラルな十分な多項式の時間目覚まし時計でもどこかに発生します。良いニュースは、私たちのマルチタスクシミュレーションでこの特定のマシンに（時間リソースの）注意事項の一部を与えたので、私たちは他の同時にシミュレートされたマシンによって（巨大な）一定の要素によってそれを遅くしました。 100％のオーバーヘッドまで残っています。そのため、この特定の「ユニバーサル」シミュレーションでさえ、多項式時に3色の例を提供することができます。 Quod Erat Promissum。
===
（このシミュレーションが3つの着色を見つけることの最適な指数でさえ保存するのに近づくことに近づくと言うのが大好きですが、それはただ真実ではないでしょう。この点で最大の問題は、「ユニバーサル」シミュレータがシミュレートされているマシンやシミュレーションをシミュレートしてシミュレーションする
単一の遷移は高価な運動です。シミュレーションは多項式時間を維持しますが、特定の指数ではありません。）残念ながら、このようなシミュレーションは、それ自身の多項式時間目覚まし時計（したがって2回遅く、また指定された入力であらゆる入力で終了することを保証する場合には、3色のタイムアルゴリズムだけです。制限時間）;そして最後のステップは構成的に構成されています。今までの建設のいかなる部分とは異なり、N、2 * N ^ 2,3 * N ^ 3、...のうちのどの多項式を知りません。私たちは十分に自由な目覚まし時計が存在するだけです。 3グラフをエンコードしない、または入力されない入力。
この回答で説明されている追加の手法の助けを借りて、普遍的なシミュレーションの方法はあなたのグラフの色の問題にさえ拡張することができます。 。メッシャーになるのは、私たちがもう「誤った回答」を簡単に除外することはできないということです。マシンが5着色を提供している場合、4着色が存在するかどうかをどうやって知っていますか？十分な解決策は、マスターアラームクロックが実行される前に、振る舞いのある子機の出力に4色が表示されます。繰り返しますが、最後のステップは非構造化されます。 P= NP。あまりにも積極的な（不十分な）多項式時間目覚まし時計を選択した場合、私たちは最適な着色を見つけることができないかもしれませんが、我々は時々待ってみたが辛抱強く十分ではない最適な塗りを出力することがあります。
o（n ^ 10000）で実行されているアルゴリズムがあると思うかもしれません。つまり、実際にはサイズののインスタンスがない> 1 。
