私は自分のアルゴリズム コースのために、Garey と Johnson による「 Computers and Intractability - A Guide to the Theory of NP-Completeness」という本を読みました。しかし、1 年後に資料を見直したときに、私はクックの定理を本当に理解していなかったことに気付きました。
証明に関しては、SAT が最初に NP であることが最初に示されている理由 (NP 完全の最初の要件) を理解していますが、「遺伝的」多項式の下で「他の」NP 完全問題を示す技術に苦労しています。 SATに変身。
誰かがこれをもっと骨抜きにした方法で説明できるかどうか疑問に思っていました.
SAT が NP 困難であること (つまり、すべての NP 問題から SAT への多項式時間の削減があること) の証明は自明ではありません。それがどのように機能するかを直感的に説明しようと思いますが、すべての詳細を調べようとするつもりはありません。そのためには、おそらく教科書を参照する必要があります。
任意の NP 言語 L を取り上げることから始めましょう。定義により、L が NP 言語であるという事実は、言語 L に対して非決定論的で多項式時間のチューリング マシン M があることを意味します。これは、マシン M が文字列 w を受け入れることを意味します。 w が L に属し、さらに M の実行時間が多項式 p(n) である場合のみです。L から SAT への還元は、特定の文字列 w に対する M の操作を本質的にシミュレートする命題式を構築できることを示すことで機能します。その式は、結果の命題式が充足可能である場合にのみ、M が w を受け入れる (つまり、w が L に属する) という性質を持っています。
これが可能であるかどうかはまったく明らかではありません。それがどのように機能するかを確認するために、TM に関連する問題を相互に軽減するための標準的な手法を使用します。文字列 w に対する M の操作について考えてみましょう。M はチューリング マシンであるため、w で M を起動すると、テープに w が書き込まれ (無限に多くの空白で囲まれている)、ある状態 q 0で、テープ ヘッドが w の最初の文字の上にあることから始まります。チューリング マシンの各ステップにより、マシンはテープ ヘッドを左または右に動かし、テープ ヘッドの下の記号を置き換え、テープ ヘッドを左または右に動かします。
TM の各ステップの直前に、マシンの状態の「スナップショット」を取得できます。そのスナップショットには、両側から無数のブランクをトリミングした後のテープ、テープ ヘッドの位置、および TM の現在の状態が含まれます。この「スナップショット」は、マシンの瞬間的な説明またはIDと呼ばれる方が適切です。（テープの内容、状態、位置）のタプルと考えることができます。
M は多項式時間 NTM であるため、入力文字列 w に対して実行する場合、p(|w|) ステップを超えて実行できないことがわかっています。ここで、p は多項式です。したがって、M が実行されると、計算には最大で p(|w|) + 1 つの瞬間的な記述 (ステップごとに 1 つ) が含まれます。したがって、M の実行は、(tape0、state0、position0)、(tape1、state1、position1)、...、(tapeK、stateK、位置K)。
これらの ID については、2 つの観察事項があります。まず、これらの ID を完全に任意にすることはできません。最初の ID がどうなるかはわかっています。テープが w を保持し、状態が q 0で、テープ ヘッドが文字列 w の先頭にある ID になります。その結果、TM が最初のステップで行うことができる非決定論的な選択のそれぞれに基づいて、2 番目の ID の選択肢はわずかしかありません。同様に、3 番目の ID の選択肢の数は有限です。その ID は、正当な 2 番目の ID から開始し、TM の 1 つの移動を適用することによって形成する必要があるためです。より一般的には、各 ID は、前の ID から始まる正当な TM の動きに従う必要があります。
第 2 に、M が w を受け入れる場合、状態がマシンの受け入れ状態であるチェーンの最後の ID がオンになるような ID のチェーンが存在する可能性があることに注意してください。逆に、M が w を受け入れない場合、ID の可能なチェーンは、受け入れ状態のマシンで合法的に終了しません。
したがって、L から SAT への還元は、本質的に、巨大な命題の公式を構築することによって機能します。各変数は、チェーン内の ID の一部 (特定のテープ セルの内容、マシンの状態、またはテープ ヘッドの場所) に対応します。次に、式は ID に関するルールをエンコードします。最初の ID は、マシンが状態 q 0を開始する ID でなければなりません。テープ ヘッドが入力文字列 w の最初の文字をスキャンすると、各 ID は前の ID に続く必要があります。式の最後の部分が 1 つあります。マシンは受け入れ状態で終了する必要があります。実際に公式のこれらすべての部分を構築するのは非常に難しいです (そのため、教科書を参照する必要があります)。ただし、最終的な結果として、式が充足可能である場合、M が w を受け入れることを示す一連の ID が存在し (つまり、w は L(M) 内にある)、充足できない場合は、M が w を受け入れる方法はありません。
お役に立てれば！