以上の最小の約数を求める問題を考える。右図の ように 2, 3, …, n で割れば計算量 O(n) で解ける。O(n) は多項式であるため、一見多項式時間に見える。 しかし入力長に対する多項式ではないため、実際の計 算量は「指数時間」である (詳細は次ページ)。 n は 2 で割れるか? n は 3 で割れるか? n は n で割れるか?
と予想している • しかし、P = NP を予想する者もおり、名著 The Art of Computer Programming を書いた大物研究者 Donald Knuth は P = NP を予想 88 Donald Knuth P≠NPを証明する 試みはことごとく 失敗している ※吹き出し内のセリフは Wikipedia の「P≠NP予想」より引用
乗を計算せよ。 整数 A, B が入力される。 A×B を計算せよ。 帰着 N×N の掛け算を考えれば、二乗問題は掛け算問題の特殊ケースになってお り、変換も多項式時間で出来る※ したがって、二乗問題は掛け算問題に多項式時間帰着可能 ※ A, B の値として N, N を入力すればいいだけなので、明らかに多項式時間 二乗問題 掛け算問題
乗を計算せよ。 整数 A, B が入力される。 A×B を計算せよ。 帰着 N×N の掛け算を考えれば、二乗問題は掛け算問題の特殊ケースになってお り、変換も多項式時間で出来る※ したがって、二乗問題は掛け算問題に多項式時間帰着可能 ※ A, B の値として N, N を入力すればいいだけなので、明らかに多項式時間 二乗問題 掛け算問題 つまり、掛け算問題は 二乗問題と同程度以上に難しい!
通常の SAT の例 3SAT の例 • x 1 = 0 または x 2 = 0 または x 3 = 1 • x 1 = 1 または x 2 = 1 • x 2 = 0 • x 1 = 0 または x 2 = 0 または x 3 = 1 • x 1 = 1 または x 3 = 1 または x 5 = 1 • x 2 = 1 または x 5 = 0 または x 6 = 1
個の条件、2 個の条件、3 個の条件など 様々あるが、まずは 2 個の場合を考える 2 個の場合、変数を 1 個追加して以下のように置き換える • x 1 = a または x 2 = b • x 1 = a または x 2 = b または y = 0 • x 1 = a または x 2 = b または y = 1 (をすべて満たす) 3SAT に 変換 ステップ 1
個の条件、2 個の条件、3 個の条件など 様々あるが、まずは 2 個の場合を考える 2 個の場合、変数を 1 個追加して以下のように置き換える • x 1 = a または x 2 = b • x 1 = a または x 2 = b または y = 0 • x 1 = a または x 2 = b または y = 1 (をすべて満たす) 3SAT に 変換 なぜ正しく変換できているか? → y が 0 か 1 かにかかわらず x 1 = a または x 2 = b が成り立つ時のみ 全条件を満たすため ステップ 1
変数 y 1 , y 2 を追加して以下のように置き換える • x 1 = a • x 1 = a または y 1 = 0 または y 2 = 0 • x 1 = a または y 1 = 0 または y 2 = 1 • x 1 = a または y 1 = 1 または y 2 = 0 • x 1 = a または y 1 = 1 または y 2 = 1 (をすべて満たす) 3SAT に 変換 ステップ 2
変数 y 1 , y 2 を追加して以下のように置き換える • x 1 = a • x 1 = a または y 1 = 0 または y 2 = 0 • x 1 = a または y 1 = 0 または y 2 = 1 • x 1 = a または y 1 = 1 または y 2 = 0 • x 1 = a または y 1 = 1 または y 2 = 1 (をすべて満たす) 3SAT に 変換 なぜ正しく変換できているか? → (y 1 , y 2 ) が 4 通りのどれであっても x 1 = a の時のみ全条件を満たすため ステップ 2
新たな変数 y を追加して以下のように置き換える • x 1 = a または x 2 = b または x 3 = c または x 4 = d • x 1 = a または x 2 = b または y = 0 • y = 1 または x 3 = c または x 4 = d (をすべて満たす) 3SAT に 変換 ステップ 4
新たな変数 y を追加して以下のように置き換える • x 1 = a または x 2 = b または x 3 = c または x 4 = d • x 1 = a または x 2 = b または y = 0 • y = 1 または x 3 = c または x 4 = d (をすべて満たす) 3SAT に 変換 なぜ正しく変換できているのか? x 1 = a または x 2 = b の時 y = 1 そうでない時 y = 0 とすれば 4 つの等式のどれかが成立の時のみ全条件を満たすから ステップ 4
新たな変数 y 1 , y 2 を追加して以下のように置き換える • x 1 = a または x 2 = b または x 3 = c または x 4 = d または x 5 = e • x 1 = a または x 2 = b または y 1 = 0 • y 1 = 1 または x 3 = c または y 2 = 0 • y 2 = 1 または x 4 = d または x 5 = e (をすべて満たす) 3SAT に 変換 ステップ 5
新たな変数 y 1 , y 2 , y 3 を追加して以下のように置き換える (7 個以上の場合も同様) • x 1 = a または x 2 = b または x 3 = c または x 4 = d または x 5 = e また は x 6 = f • x 1 = a または x 2 = b または y 1 = 0 • y 1 = 1 または x 3 = c または y 2 = 0 • y 2 = 1 または x 4 = d または y 3 = 0 • y 3 = 1 または x 5 = e または x 6 = f (をすべて満たす) 3SAT に 変換 ステップ 6