共通するパターン

NP 困難性の証明、そして一般的には全ての多項式時間帰着には、共通するパターンがあります。問題 \(X\) から問題 \(Y\) への多項式時間帰着には次のステップが必要です:

  1. \(X\) の任意のインスタンス \(x\) を \(Y\) の特殊なインスタンス \(y\) に変換する多項式時間アルゴリズムを示す。

  2. \(x\) が \(X\) の "良い" インスタンスならば \(y\) は \(Y\) の "良い" インスタンスであると示す。

  3. \(y\) が \(Y\) の "良い" インスタンスならば \(x\) は \(X\) の "良い" インスタンスであると示す (通常最も難しくなるのはこの部分)。

もちろん正しい帰着を開発するときにはこれらの作業を一つずつ処理するのではありません。上手く行くと思われるアルゴリズムを書くところから初めてその後に正しさを証明するというやり方はまず上手く行かず、試験のように時間が限られているような状況では特にそうです。アルゴリズムの開発、"if" の証明、"only if" の証明は同時に行わなければなりません。

晩年の Ricky Jay の言葉を借りるなら1、「これは後天的に身に着けるスキルです」

多くの生徒を困惑させるのは、帰着アルゴリズムが "片方向にしか"、つまり \(X\) から \(Y\) にしか帰着を行わないにもかかわらず、正しさの証明は "両方向に" 必要となる点です。しかしよく考えてみれば、証明は対称的ではありません。"if" の証明は任意のインスタンス \(x\) を扱うのに対して、"only if" の証明は帰着アルゴリズムによって生成される \(Y\) の特殊なインスタンスだけを扱うからです。この非対称性をうまく利用することが正しい帰着を設計するための鍵です。

あるインスタンスが "良い" ことの証明を「証拠 (certificate)」と呼ぶようにすると分かりやすいでしょう。例えば \(\textsc{CircuitSAT}\) のインスタンスに対する証拠は電球を灯らせるような入力であり、\(\textsc{SAT}\) や \(\textsc{3SAT}\) のインスタンスに対する証拠は式を充足させる真偽値割り当てです。この言葉を使うと、\(X\) から \(Y\) への帰着に必要なのは次の三つのアルゴリズムです:

二番目と三番目のステップにおける \(x, y\) は一番目のアルゴリズムの入出力のことを指しています。証拠の変換は両方向に行える必要がありますが、インスタンスの変換はそうではありません。\(Y\) のインスタンスを変換する必要はなく、\(Y\) の任意のインスタンスについて考える必要もありません。また多項式時間で実行されなければならないのは最初のアルゴリズムだけです (ただし実際の証明ではまず間違いなく二番目と三番目のアルゴリズムが最初のアルゴリズムよりも単純になります)。

例えば \(\textsc{CircuitSAT}\) から \(\textsc{3SAT}\) への帰着は三つのアルゴリズムからなります:

この帰着が上手く行くのは、任意の回路 \(K\) が高度に構造化された 3CNF 式 \(\Phi_{3}\) に変換されるためです。\(\Phi_{3}\) の構造によって、\(\Phi_{3}\) を充足させる真偽値割り当てが必ず \(K\) を充足させる入力から来るようになります。任意の 3CNF を考える必要はありません。

同様に、\(\textsc{3SAT}\) から \(\textsc{MaxIndSet}\) への帰着は三つのアルゴリズムからなります:

ここでも最初の変換によって \(\Phi\) が高度に構造化されたグラフ \(G\) と整数 \(k\) に変換されます。このグラフ \(G\) の構造によって大きさ \(k\) の独立集合が必ず \(\Phi\) を充足させる真偽値割り当てから来るようになります。任意のグラフあるいは任意の大きさの独立集合を考える必要はありません。

  1. 1996 年のオフブロードウェイのショー Ricky Jay and his 52 Assistants より。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。