確率的検査可能証明とその応用

（ＬＡ会誌へ寄稿）

聞いたことのある方も多いかもしれないが， 確率的検査可能証明 （Probabilistic Checkable Proof，以下 PCP と略す） という概念が一昨年に発表され， かなり話題になった． Arora 等 [ALMSS92] が， この概念を用いて NP の新しい特徴づけを行なったのだが， その結果が大評判になったからである． 正確な解説は [OO94] などをご覧頂くとして， ここでは， その特徴づけの意味とその応用について， かなり大雑把な解説と大胆な私見 （つまり，いい加減な説明と無責任なコメント） を述べることにする．

私は 構造的計算量理論（Structural Complexity Theory） などと呼ばれている分野の研究を主に行なっている． 同じ計算の複雑さの理論でも， 効率良いアルゴリズムの開発を目指していたり， あるいは具体的な計算の複雑さの研究をしている場合には， 目標の問題が決まっていて， その難しさが重要となる． 一方， 我々の場合には， ある種の問題に共通する「難しさ」自身が興味の対象だ． その「難しさ」の特徴は何かを探り， それによってその「難しさ」がどの程度のものなのか， あるいは， どこに難しさの本質があるのか， などを明らかにしていくのが我々の目標なのである． Arora 等の結果も， クラス NP に対する そうした新しい特徴づけの一つといえよう．

１．NP 問題の証拠に対する確率的検査

• F が Yes の論理式 ⇒ ∃a_1,..., a_n すべての C_i が真,
• F が No の論理式 ⇒ ∀a_1,..., a_n ある C_i が偽.

ただ， 「全部の C_i をチェックするのも面倒だ」 という場合もあるだろう． だからといって， 適当な C_i をチェックして納得するわけにはいかない．

もっともここだけの話しですが， 私はテストの採点で時々この手を使いますが ...

定理． 与えられた F に対して， 次の性質を満たす F' が（多項式時間で）構成可能．

1. F が充足可能 ⇔ F' が充足可能．
2. F' は， F'(X'_1,...,X'_{n'}) = C'_1 ∧ … ∧ C'_{m'} という形をしており，
   • F' が充足可能 ⇒ ∃a_1,..., a_{n'} すべての C'_i が真,
   • F が充足不可能 ⇒ ∀a_1,..., a_{n'} 真となる C'_i は全体の 10% 未満.
   （注：実際の定理では 10% よりもっと小さい定数が使われている）

3SAT 問題に限っていえば， F' と F はつねに同じ答えとなる． つまり F' は本質的には F と変わらない． ただ大切なのは， 「F' の充足解（Yes の証拠）の候補のうち， 本当に F' を真にするもの以外は， どんなに多くても C'_1,...,C'_{m'} の 10% 未満のクローズしか真にできない」 という点である． そこで a_1,...,a_{n'} が本当の充足解かどうかを調べるのに， C'_1,...,C'_{m'} の中からランダムにクローズを数個選んで， それが a_1,...,a_{n'} で真になるかを調べれば， かなりの確率で正しく判定できることになる． つまり Yes の証拠が確率的に検査可能なのである．

ここでは 3SAT 問題を考えたが， どのような NP 問題を考えても， 確率的に検査可能な Yes の証拠の与え方がある． しかも， 自然な Yes の証拠が与えられれば， それを多項式時間以内に 確率的に検査可能な証拠に変換することもできる． これが Arora 等の定理なのである．

２．この新しい特徴づけの応用

たとえば OPT-3SAT 問題を例にして考えてみよう． これは， 「与えられた 3CNF 論理式, F = C_1 ∧ … ∧ C_m, に対して， なるべく多くのクローズを真にするような真偽値割当てを求めよ」 という問題である． F が充足可能な場合には， もちろん， m 個の全てのクローズを真にするような真偽値割当て （すなわち充足解） が答えになる． 一方， 充足可能でない F に対しても， できる限り多くのクローズを真にするような真偽値割当てが答えである．

一般に NP 型最適化問題は ベースとなる NP 問題よりも難しい． たとえば， OPT-3SAT 問題も， 3SAT 問題が多項式時間で解けない限り， 多項式時間で解くことは不可能だ． しかし近似解ならば求められるかもしれない． たとえば与えられた F に対して， 最適解だと k 個のクローズを真にできたとする． そのとき k 個は無理としても， その 90% 減の 0.1k 個（以上）のクローズを真にする解 ,--- 0.9-近似解 ---, は容易に求まるかもしれない． 最適解に対して， 少なくとも (1-\varepsilon) 以上の近似解を保証するアルゴリズムを， ε-近似アルゴリズムという． はたして， OPT-3SAT 問題に対して， 多項式時間の 0.9-近似アルゴリズムは存在するのだろうか？ 実は， 前述の定理から， P ≠ NP ならば， 0.9-近似アルゴリズムも存在しないことが示せるのだ．

理由は簡単． 仮に OPT-3SAT 問題に対し， 多項式時間の 0.9-近似アルゴリズムがあったとしよう． これをアルゴリズム A と呼ぶ． この A に対して， 先ほどの定理で得られた F' を入力してみると，

• F' が充足可能 ⇒ F' →（入力）→ [A] →（出力）→ 少なくとも 0.1m' 個のクローズを真にする解
• F' が充足不可能 ⇒ F' →（入力）→ [A] →（出力）→ 高々 0.1m' 個未満のクローズを真にする解

えっ， 「なぜ F' が充足不可能のときに得られる近似解が， 高々 0.1m' 個未満のクローズしか真にできないか？」 って！？ そもそも最適解でさえ， 0.1m' 個未満のクローズしか真にできないんですよ． 近似解にそれができてたまるもんですか！

以上のようなわけで， （P = NP とならない限り） OPT-3SAT 問題に対しては， ある ε までしか ε-近似アルゴリズムが作れない． さらに OPT-3SAT 問題は， MAX SNP と呼ばれる NP 型最適化問題の代表例だったので， この否定的結果から， MAX SNP 型問題に対しても同様の否定的な結果が得られる． このように， Arora 等の結果は， NP 問題の「難しさ」に関して， 我々に新しい知見をもたらしてくれたのである．

確かに Arora 等の結果は， 近似不可能性を証明するための重要な道具を我々に提供してくれた． 実際， 昨年は多くの研究者が， その道具を使って様々な NP 型最適化問題の近似可能性を議論している． しかし NP の証拠の検査に対するこの新しい考え方は， 単に近似不可能性を証明するための道具に過ぎないのだろうか？ 私はもっと重要な応用が隠されているのではないか？ という気がしてならない．

彼らの開発したテクニックは， 何も NP 問題の証拠を調べるためだけのものではない． 直観的にいえば， 「どんな証明でも， うまく変換してやると， その中のランダムに選んだ数箇所を調べるだけで， 高い確率で正しさを判定できる」 のである． だから， 長い数学論文でも， この方法を使って変換してやれば， 容易に正しさをチェックできる． もっとも， チェックを誤る確率も入ってくるので， そんな応用は数学会では使ってもらえないだろうが， たとえば， プログラムの検証やハードウェアのテストに使えないだろうか？

あるいは， もっと大げさにいえば， 新しいタイプの符合理論の始まりかもしれない． 彼らの提案したテクニックは一種の符合化法ともみれる． 従来の符合化法では， 対象となるビット列に意味を考えていない． どのようなビット列でも誤りを検出／復元するように符合化されている． それに対し， 彼らのテクニックは， 「Yes の証拠」 という論理的に意味のある列の符合化なのである． 意味を考えることにより， より効率の良い， より復元力の高い符合化をすることができるはずだ． 彼らのテクニックは， そうした研究への足掛かりになるのではないだろうか？

どちらにしても， こうした応用を手がけるには， 彼らのテクニックの原理をすみずみまで理解しなければならない． しかし， お恥ずかしいことに， こうした解説を書いていながら， いまだにわかっていないことが多い． 頑張らなければ！

参考文献

• [ALMSS92] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy: Proof verification and intractability of approximation problems, in Proc. 33rd Annual Sympos. on Foundations of Computer Science, IEEE (1992), 14--23.
• [OO94] 太田和夫，岡本龍明： クラス NP の新しい特徴づけ， 情報処理 Vol.35, No.1 (1994), 55--68.