YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 06-40 Making a SAT graph

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. 3-COL問題はNP困難であると証明して見せましょう

  2. もし3-COL問題が多項式時間の問題であるなら
  3. 3-SAT問題もまた多項式時間で解けます
  4. 方法としては3-CNFの式をグラフを用いて
    3-COL問題に当てはめます
  5. 簡単に当てはめることができますよ
  6. グラフが3色に当てはまる場合元の式が
    3-CNFの式である限り充足可能になります
  7. CNFとは乗法標準形の略です
  8. 前にも出た式と同じくn個の節からなる式です
  9. そして各節には3つのリテラルがあります
  10. 3-CNF問題を解きたい場合
  11. その式が充足可能である限り
    色分け可能な3-COL問題に変換できます
  12. 面白そうな挑戦ですよね
    ではグラフを作成するところから始めましょう
  13. 式内の可能なすべてのリテラルのために
    ノードを用意しましょう
  14. 異なる変数がk個分 実体化しました
  15. 変数がk個に節がs個ありますが
    ノードを3つ追加しましょう
  16. それぞれ真、偽、スラックとし
    他のノードをつなげましょう
  17. 各リテラルと真と偽をスラックにつなげます
  18. 真と偽の間もつなげます
  19. 真と偽とスラックは三角形でつながりました
  20. これを3つの色に置き換えられるかどうかですが
  21. 置き換えは真、偽、スラックに行います
  22. スラックを赤に真を青に偽を黒にします
  23. さてこのグラフのリテラルですが真か偽
    つまり青か黒に置き換えられます
  24. 3-COL問題に置き換えが可能な場合です
  25. どうやらうまく真理値の割当てができそうですね
  26. 気をつけていただきたいのはリテラルV1と
    リテラルnotV1はどちらも真や偽になったりしません
  27. ですがグラフ彩色問題では修正は簡単に行えます
  28. エッジでつなげましょう
  29. 各変数にエッジを与えリテラルをペアにします
  30. これでどちらも真や偽になったりしません
  31. ここで変数に青 そうでないものに黒
  32. または変数に黒 そうでないものに青を割り振ります
  33. これが真理値の割当てです
  34. 3-COLは真理値の割当てに
  35. 真理値の割当ては3-COLに対応します
  36. 今のところ3-SAT問題を図表で理解するのは順調ですね