【シプサ】7 時間の複雑さ (その4)

リハビリかねて、こつこつ、というより、ちょいちょい。

• Φ=(¬x∧y)∨(x∧¬z)を0,1,0が充足するか?
  
  
  
  • (¬0∧1)∨(0∧¬0)
    
  • (1∧1)∨(0∧1)
    
  • 1∨0
    
  • 1
    
  • お、充足。
    
  
  
  
• Cook-Levinの定理の紹介。
  
• 多項式時間帰着可能性の導入。
  
• conjunctive : 結合する; 合同の, 共同の;
  
• 定理7.32 3SAT <=P CLIQUEの確認。
  
  
• 「定理7.36 BがNP完全であり、かつNPに属するCに対してB <=P Cならば、CはNP完全である。」
  
  
  
  • 自分なりに考える。
    
  • BはNP完全だから、B∈NPであり、NPに属するすべてのAが、A <=P Bである。
    
  • B <=P Cだから、たぶん、上のAについて A <=P Cである。
    
  • 前項の後半は、NP完全の定義そのものなので、CはNP完全である。
    
  
  
  
• SATのNP完全性を示すのはごつそうだ。
  
• 今回は、玉砕覚悟で自分なりに考えてみる。
  
  
• 「定理3.37 SATはNP完全である。」
  
  
  
  • SATはNPに属するか?
    
    
    
    • brute-forceで非決定でいけばいいのではないか。
      
    • 入力がn個のリテラルを含むとする。
      
    • すると入力の全体長はたかだかnの定数倍だ。なので、このnで考える。
      
    • n個のリテラルはそれぞれ0または1でありえる。
      
    • その割り当てを非決定的に実施する。
      
    • 矛盾した割当てとなったらその枝は拒否する。
      
    • すべてのリテラルに割当てが完了したところでその割当ての論理演算を実施する。
      
    • 前項が真になるならこのTMは受理する。
      
    • 受理の枝がひとつもなければこのTMは拒否する。
      
    • 各枝は、まあ、多項式時間のようだ。
      
    • というわけで、このTMは非決定性多項式時間機械である。
      
    • ゆえにSATはNPに属する。
      
    
    
    
  • 次に任意のA∈NPについて、A <=P SATが成り立つといえるかどうか。
    
  • A∈NPなので、Aを判定する非決定性多項式時間TM Nが存在する。その多項式時間をn^kとする。
    
  • 計算状況を並べた(n^k) * (n^k)の表をタブロー(tableau)と呼ぶ。各状況の頭とお尻は'#'とする。
    
  • tableau: (小説などの)絵画的な描写
    
  • 1つのタブローがひとつの計算の枝に対応する。
    
    
  • AからSATへの多項式帰着写像fを構成する。
    
    
    
    • 入力wから論理式Φを生成する。
      
    • wがNに受理されるなら、ΦはSATに属する。
      
    • wがNに受理されないなら、ΦはSATに属さない。
      
    • Nの仕様として、状態：Q、テープアルファベット：Γとする。
      
    • C=Q∪Γ∪{#}とする。
      
      
    • う、これ以降、しんどい。次回へ。
      
    
    
  
  

次回は、SATのNP完全確認の途中から。