注：PCP は Probabilistically Checkable Proof の略です．
このページは， 数学セミナーに連載の（０３年７月号〜１０月号） 「ＰＣＰ：驚異の証明検証法」を補足するためのページです． まずは， 連載中の記事をご覧下さい．
渡辺治のその他のページ
Created by O. Watanabe, June 2002.
内容
この連載では， 説明を簡潔にするために， 不正確な説明で済ましてしまったところがいくつかあります． 説明をはしょった点を示し解説を補足しましょう． （※以下では，数セミの記事を「本文」と呼ぶことにします．）
不正確な説明で済ませてしまった点は，次の３か所です． （本文中では「２か所」と書きましたが， もう「１か所」ありました．）
以下，数セミ本文より（７月号，p. 51，右カラム）．
では， 先生は，この点をどのようにチェックすればよいでしょうか？ 簡単です． 回答された値を方眼紙上にプロットし， それが 2 次曲線となっているかを見ればよいのです． たとえばＫ君の回答をプロットすると， (u,G(u)) が直線上の点であること （すなわち G が 1 次関数であること） が一目瞭然です． だから， 元となっている gK も 2 次関数でしょう．
この最後の文は正しくありません． gK が，もっと複雑な関数であっても， たとえば，高次関数であっても， その高次の項がキャンセルされて， G が 2 次以下の関数となる場合もあるからです．
実は， 生徒が（宿題で）提出する表は， 関数 G の値の表ではなく， 元となっていた関数 g の値の表だったのです． G の値は，その表から計算するのです． ただ， 「G の値を g から求める」というプロセスを省略したかったので， 記事では， 関数 G の値の表を提出してもらうことにしたのでした．
さて， g の値の表が提出されるのであれば， それをプロットすれば， g が 2 次以下の関数であることは確かめられますよね． （詳しくは次の説明を．）
上の点は，かなり細かなことでした． 一方，今度のは，非常に本質的なことです．
本文の例では， 宿題の正しさを確かめるのに， 生徒を呼び出して 7 回質問すればよいように書きました． （正確には， 生徒に質問するのは 6 回です． 最後の 7 ラウンド目のチェック (b) は， 生徒の宿題（拡張 G 値表）にあたって調べます．） ところが， もう少ししらべなければならなかったのです．
生徒が提出した拡張 G 値表から， 元となっている関数 G の次数が， 本当に 2 次以下であるかをチェックしなければならなかったのです．
※先の説明にもありましたが，本当に提出してもらうのは関数 g の値の表です． ただ， 本文と合わせるため（説明を簡単にするために）， 以下でも G を中心に説明することにします．
これは８月号の解説で明らかにされることなのですが， 一連のチェックがうまくいくためには， 各ラウンドで調べたい関数（例えば，h と h_{p}）が， 両者とも 2 次以下である，という点が本質的なのです．
これは 7 ラウンド目のチェック (b) も同様で， h_{p7,p6,...,p2} が 2 次以下であり， しかも拡張 G 値表の元となっている関数 G が 2 次以下の場合， たった 1 個の点 p1 で， 値をチェックすることにより， 高い確率で違いを見い出せるのです． もし，拡張 G 値表を作るときに使った関数が， もっと複雑なものだったら， あるいは， そもそも元になる関数など無しに表を作っていたら， たった 1 点 p1 だけでチェックはできません．
拡張 G 値表は 2 次以下関数 G によって作られた表でなければならないのです．
本文や（１）でも簡単に「プロットすれば」と述べました． たしかに， 拡張 G 値表が， 何らかの 2 次以下の関数 G の値であれば， 点をプロットすれば， それが 2 次曲線になっているでしょう． ただ， それが本当の 2 次曲線かどうかはどうやって調べればよいのでしょうか？
それには， いわゆる曲線の当てはめ（fitting）をします． つまり， プロットした点に当てはまるように， 関数 ax^2 + bx + c のパラメータを決めればよいのです． （最近は便利です： gnuplot などのグラフ描画ソフト についている fit コマンドを使うと簡単にできますよ．）
さて，その場合にも， もらったデータ（拡張 G 値表）をすべて見る必要はありません． やはり，ランダムに選んだ複数個の点で十分で， しかも， その個数は次数（我々の場合には 2 次）の高々数倍でよいのです． （詳しい議論は参考文献 [2] を参照して下さい．）
以上をまとめると， チェックの方法は次のようになります．
拡張 G 値表から値をランダムに数箇所取ってくる． それに 2 次関数 ax^2 + bx + c を当てはめる． うまく当てはまったらＯＫです．
たしかに「うまく当てはまった」らＯＫですし， また， 正解を正しく答えていれば， うまく当てはまるはずです． ただ， 2 次関数に近いのだけれども， 実は複雑な関数があるかもしれません． 2 次関数との差が微妙なので， 上のチェックでも違いは見出せないかもしれないのです． 一方， 実際は複雑なので， 様々な関数 h_{p7,...,p2} に対して， 第 7 ラウンドのチェック (b) をパスしてしまうかもしれません． そんな巧妙な関数から作った拡張 G 値表を使われたらどうでしょうか？
それでも大丈夫なのです． というのも， 上のチェックをパスするのならば， 「うまく当てはまる」パラメータ a, b, c が見つかるはずです． そうしたら， 拡張 G 値表などを使わずに， そのパラメータで定義された 2 次関数を G として使えばよいのです．
本文では， 「間違いを見逃す確率は高々 7(2/40) (= 0.35) 」（p. 54，右カラム） と書きましたが， 実際には高々 1-(1 - 2/40)^7 (= 0.30...) であることも示せていました． （土岡さん，指摘ありがとう．） 詳しくは８月号の補足（以下の（２））をご覧下さい．
不正確な説明で済ませてしまった点は，次の２か所です．
先月号の説明でも，関数 g ではなく， まとめた関数 G の話を中心にしていましたが， ８月号の説明では，次のように g をまったく無視した説明になっています （７月号，p. 58，左カラム）．
Ｗ先生の宿題
次の等式を満たす高々 2 次の関数 G があることを示せ．ただし，関数 G の定義式ではなく， G(-2413), ..., G(2540) の値の表を提出すること．
S = G(0) 〜 G(127) の総和 = 0
これはちょっとやり過ぎ（単純にしすぎ）だったかもしれません． この号から見た方は 「何でこんな簡単なことが宿題になるの？」 と思われるかもしれません． 恒等的に 0 となる関数で十分答えになっているのですから．
本当は，こうではなくて g(u+1) - g(u-1) - 2u*u という， 関数 g に対するもう少し複雑な式を考え， この式の u = 0 〜 u = 127 の総和を 0 にする関数 g を示せ， という問題でした． その式 g(u+1) - g(u-1) -2u*u を G(u) とおいたのでした．
それでもまだ単純かもしれません． つまり， g(u+1) - g(u-1) - 2u*u = 0 となるように g(u) を定義するのも 難しいことではないからです． ただ， そこは目をつぶって下さい． つまり， そんな関数を考えるのは「とても難しい」と思って下さい． そうなる例は９月号で紹介します！
もっと一般的にいうと， 関数 g に対する何らかの関数 H(g) が予め決められており， しかも u の範囲も（たとえば u = 0 〜 u = M と）決められていたとして， そのときに
本文（８月号 p.59）で， 間違った宿題を出した J 君がうまく言い逃れられる確率 （つまり，J 君の誤りを見過ごす確率） を議論し， それが 7*(2/40) = 0.35... 以下であることを示しました． けれども 1- (1-2/40)^7 = 0.30... 以下であることを示すことも， そう難しくありませんでした．
その理由を簡単に述べてみましょう． J 君がうまく言い逃れられるためには， 最後のラウンドも含め， 7 回の p_i の選択のうち， どれかで
逆に言えば， どのラウンドでも (*) が成立しなければ， J 君は言い逃れすることはできません． 各ラウンド i において， ランダムに選んだ p_i に対して (*) が成立しない事象を Q_i とすると， すべてのラウンドで (*) が成立しない確率は，
条件付確率は， 多くの場合，見積もるのが難しいのですが， 今回は，この確率がつねに (1 - 2/40) 以上であることが示せます． これは， ラウンド i においてチェックされる式の総次数が つねに 2 以下だからです． 過去の状況（Q_1, ..., Q_{i-1}）がどうであろうと， その事実は変わりません． したがって， (*) の 2 つの関数に対して同じ値を取るような p_i は高々 2 個であり， ランダムに選んだときに， たまたま p_i がそのどちらかである確率は 2/40 以下， したがって， その逆が起こる確率は 38/40 以上なのです．
これを上の評価式に代入すると， すべてのラウンドで (*) が成立しない確立は次のようになります．
不正確な説明で済ませてしまった点は，次の２か所です．
本文（９月号 p.48 右のカラム）で， 次のように述べました．
さて，その証明は何でしょう？．．．
その「証明」は充足割り当てを示す以外によい方法がないと予想されているのです．
しかし， これは不正確な言い方です． 実際， 以降ではＰＣＰによる「よりよい証明」を解説しているのですから， ある意味で矛盾していますよね． ここで述べた「よい方法がない」というのは， 正確には「充足割り当てより本質的に短い証明はない」という意味です．
ＰＣＰは効率的にチェックできるという意味で「よりよい証明」になっていますが， そのために， 証明の長さ自体は充足割り当てより，はるかに長くなっています．
それでは，なぜ「充足割り当てより短い証明はない」のでしょうか？ （正確には，そう思われているのでしょうか？）
それは「充足可能性問題」（ＳＡＴ問題）の難しさに関係しているのです．
たとえば，n 変数の論理式の充足性を調べたかったとします． その場合， もっとも単純な方法は， すべての可能な割り当てで試してみることです． つまり， すべての可能な割り当てを実際に代入し， どれかで真になるかを試してみるのです． その場合の計算時間は 2 の n 乗に比例したものになります． 多くの研究者が努力していますが， この単純なものより格段に速い方法はまだ見つかっていません．
たとえば， 今回の解説で対象としている 3-和積式 （3 つの命題変数からなる和項の論理積からなる論理式）に限ったとしても， 2 の n/2 乗くらいのものも見つかっていません！ （近くまではいっているのですが．．．） というわけで， 2 の n/100 乗くらいのものは，まだまだ先です．できないかもしれません．
ところが， もし「充足性の証拠」として， 充足割り当てより，はるかに短い証明があったとすると， その証明の候補を全部あたってみることで， 従来のものより格段と速く充足性が判定できてしまいます．
たとえば， 充足割り当ての表現には n ビット必要ですが， n/100 ビット程度で表現できる「充足性の証拠」があったとしましょう． すると， その証拠の候補をすべて試してみる （それが実際に証明になっているかをチェックしてみる）ことにより， 充足性を判定することができます． しかも， すべての候補は高々 2 の n/100 乗個です． 証明かどうかのチェックに必要な計算時間にもよりますが， もし， それが 2 の n/100 乗に比べてはるかに小さければ， ほぼ， 2 の n/100 乗の計算時間の判定法が得られてしまうのです．
この連載ではＰＣＰを「驚異の証明検証法」として紹介してきました． ところが複数の方から「証明の検証」に対する違和感を寄せられました． １０月号では，ＰＣＰの背景を解説するとともに， そうした違和感に対してお応えしようと試みたのですが， 言葉足らずだったところもあります． そこで，この点について少し補足いたします．
批判：証明の検証だって？ 証明とはそもそも厳密に正しいもののはず．つまり検証されたものが証明なのでは？
確かにごもっとも． 正確には「証明の候補に対する検証」と言うべきです． でもそれでは長ったらしくなるので， 短く「証明の検証」といってしまったのです．ご理解ください．
批判：命題論理式（とくに３-和積式）の充足解のチェックを 「証明の検証」というのは大げさじゃあないですか？ 「検算」とでも言うべきなのでは？
最初の例題（総和のチェック）は確かに「検算」でした． 一方， 命題論理式ではありますが， 論理式の充足解は， その正当性（充足性）を示す根拠， つまり「証明」と言ってもよいと思うのです． ただ， ３-ＳＡＴ問題に登場するような３-和積式が， あまりに単純なので， 「証明」という言葉に違和感を感じるのではないでしょうか？ しかし， そう単純でもない，ということを説明していきましょう．
まず次の事実を述べておきます． （証明は省略．たとえば拙著をご覧下さい．）
定理： すべての命題論理式は （３-ＳＡＴ問題の意味で同値な） ３-和積形の形に簡単に（ほぼ線形時間で）書き直すことができる．
どんなに複雑な式でも構いません． 命題論理式ならば， (X1 ∨ X3 ∨ ¬X4) (¬X5 ∨ X3 ∨ X1) ... のような 単純な和項の積の形に直すことができるのです． （論理記号の意味は，∧（かつ），∨（または），¬（否定）です．）
以下では， ３-和積式に対する充足解を「証明」とみなすことができる， という点を次の２つの観点から述べていきます．
そもそも「証明」とは何でしょうか． 公理，あるいはすでに証明された定理を元に， 新たに証明したい事実を論理的に導出していくことでしょう．
公理や定理は， 仮定と結論の形をしています． たとえば 「A1 かつ A2 ならば B」といった形です． これを論理式で書くと
A1 ∧ A2 ⇒ Bです． さらに ⇒ を∧，∨，¬ だけで書き直すと
¬( A1 ∧ A2 ) ∨ B ≡ ¬A1 ∨ ¬A2 ∨ Bとなります． つまり「和項」になるのです． 公理や定理をデータベース化したとすると， こうした和項の集まりになると考えてもよいでしょう． 証明では， 使用する公理や定理は「すべて成り立つ」ことが大前提です． つまり， 上記の和項の集まりは， 実はすべてを論理積で結んだ巨大な式が「成り立つ」ということです． （この「成り立つ」というのは， 恒真（どんな割り当てでも真）ではありません．充足可能であればよいのです．）
もちろん，これは大ざっぱな見方です． 実際の公理や定理では， A1 や B も複雑な式や文になっているはずです． それらを厳密に表わすには， 単純な命題変数では不十分で， 変数付きの「述語論理式」が必要になります． たとえば 「ある自然数で P(x) が成り立つ」 を表わすための式 ∃x∈N[ P(x) ] のような論理式です． ただこれも， 有限の範囲であれば， 命題論理式に書き下すことができます． （一方， 無限を扱うことはできません． この点は目をつぶってください！）
さて，ある定理を証明したいとします． その背景となる数学分野の公理系を 上に述べたように巨大な式で表わしたものをΦとしましょう． また， 証明したいことが B1 ∧ B2 だったとします． この証明を考えてみましょう．
こういった場合の常套手段は背理法による証明です． つまり， 証明したい式の否定を仮定し， それが矛盾することを示すのです． ここでは
¬( B1 ∧ B2 ) ≡ ¬B1 ∨ ¬B2を仮定します． さて， 「矛盾」とは，何に対する矛盾でしょうか？ 正確には， 前提となる数学（ここではΦ）に対する矛盾ですね． つまり，
Φ ∧( ¬B1 ∨ ¬B2 ) --- (1)が真に成り得ない， 言い換えれば充足不可能であることを示すのが「証明」なのです．
逆に上の式 (1) が充足可能だったらどうでしょう． これは 「¬B1 ∨ ¬B2 を付け加えても矛盾が生じない」 ということです． つまり， ¬B1 ∨ ¬B2 となる場合もある， すなわち元の式が成り立たない場合があり得るわけです．
そう解釈すると (1) の論理式に対する充足割り当てにも意味が出てきます． それは証明したかった式 B1 ∧ B2 が成立しないことの証明 --- 反証 --- になっていたのです． 以上の議論から
主張： （世の中の多くの）反証は 命題論理式（３-和積式）に対する充足割り当ての形に書けると主張できるのではないでしょうか． （先に述べたように， 無限を含む論証の場合には適用できません． ですから「世の中の多くの」とは言えませんかね．．．）
一番目の主張は直接的ですが，少し不完全でした． 一方，二番目の主張は，ある意味，完全です． 数セミ本文（p.55）でも， この点について述べたのですが， 簡単にしかふれられませんでした． 以下に補足しましょう．
この議論には， ３-ＳＡＴ問題のＮＰ完全性の証明が必要です． また， 数学基礎論という分野で研究され培われてきた「証明」に対する考え方も重要です． 詳しくは参考文献を参照頂くとして， そのエッセンスをまとめてみましょう．
まず 「数学の証明とは何ぞや」というところから始めましょう． これは先にも述べましたが， 公理，あるいはすでに証明された定理を元に， 新たに証明したい事実を論理的に導出していくことです． この「公理」と「論理的な導出」について， 数学基礎論ではいろいろと研究されてきました． その結論を簡単にまとめると， 以下のようになると思います．（ちょっと不安ですが．．．）
もちろん， これはあくまで信念であって， このこと自体に数学的な証明を与えることはできません． また， 数学のすべての分野のすべての定理の証明を， 機械的な導出過程として書き下したわけでもないでしょう． 上記の考え方は極めて自然であり， 現在， 多く数学者に受け入れられていることだと思います．
さて， 証明が機械的に記述されるのであれば， 与えられた証明に対し（正確には，証明の候補です！）， その導出に誤りがないかをチェックするプログラムを作ることも可能でしょう． たとえば， 群論の言明に対する証明（の候補）をチェックするプログラムを G とします． 具体的には次のようなプログラムとしましょう．
プログラム G の入力：ここで， 導出ステップ数に「t 以内」という制限を設けましたが， これ以後の議論の都合上，導入したものです．
言明（定理の候補） x ，自然数 t ， その証明の候補 w．
ただし w の導出過程の長さは t ステップ以下とする．
プログラム G の出力：
w が x についての正しい導出のとき ⇒ 1 を出力
その他の場合 ⇒ 0 を出力
この証明検証プログラム G に対して， ３-ＳＡＴ問題のＮＰ完全性の証明の技法を使うと次の定理を示すことができるのです．
定理： 与えられた言明 x と自然数 t に対し， 次のような性質を持つ命題論理式（３-和積式）F を定義できる．∃ w [ G( x, t, w ) = 1 ] ⇔ F は充足可能
しかも， F の充足解を見ると， そこには正しい（G を満足させる）w が符号化されていて， そこから w を容易に再構成することができるのです． そうであれば， 充足解を証明と言ってもよいでしょう． これが二番目の主張でした．
ＰＣＰについて書かれた教科書で， 日本語のものはまだ無いと思います． ただし， 基本的考え方は， たとえば，以下の文献 [1] の IP = PSPACE の項で説明されています． （ちなみに [1] は，計算機科学全般に関する良い教科書ですよ．）
英語では，たとえば文献 [2] が， 詳しく，かつ丁寧に解説しています． この記事を書くときも，この本を参考にしました． 計算の複雑さの理論に興味を持たれた方は， 入門書として文献 [3] をどうぞ．
この連載の各記事の初稿に対して， 次の方々から間違いの指摘， わかりにくい点についてのコメントを頂きました． お礼を申し上げます．