読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

できないことを言うときは用意周到に

前の記事: http://azapen6.hatenablog.com/entry/2012/12/22/031000

今回と次回の話では、前回掲げた「妥協するのも悪くない」という主張の裏をとって、「妥協しないとお手上げ」という場合が実際にあることを示します。問題は前回に引き続き、アリスとボブがそれぞれ巨大なデータのコピーを持っていて、それらが完全に一致していることを少ない通信量で確かめるというものです。前回の内容は、乱数を使って誤りが生じるを可能性をほんの少し妥協すれば、それを実現する方法を具体的に構成できるというものでした。

これから目指すことはいわば前回の裏で、乱数を使わないで完全なチェックを求める限りは、どうやっても対象のデータをそのまま送信するのと通信量の意味で差をつけられない、ということを証明します。これは「通信複雑性」という領域の初歩的な問題であり、様々な計算モデルの能力の限界を証明することに応用があります。ここではそこまで深入りしませんが、通信の問題が計算の難しさと関係しているということを、頭の片隅にでも入れて読んで頂くと、このようなお話にも深みが増すかと思われます。

さて、我々は困難性(または不可能性)の証明に入ろうとしているわけですが、そのときには議論をするための枠組みをきちんと決めてやる必要があります。それを怠って「どうやっても無理」と主張したところで、「あなたが考えに及ばなかったことも含めて、すべての可能性を尽くしたとでも言うのか?」とでも反論されるのがオチでしょう。これでは「悪魔の証明」に陥ってしまいます。それは実行不可能ですから、枠組みなき困難性の証明は科学的に意味を為しません。歴史的には、5次方程式の一般解の公式を作るのは不可能であるというアーベルやガロワの主張が当初は認められなかった*1という例があります。枠組みをきちんと決めてやることは、ネガティブな結果を出すときには特に重要なのです。

もっとも、今回の話は、内容に踏み込む前の面白くない部分を抜き出したものかもしれません。筆者においては、論文などを書くときに一番面倒で投げ出したくなる部分です。ただ、通信複雑性の話に入るためにはどうしても必要な部分なので、できれば次回まで飛ばさずに読んで頂けると幸いです。

通信による計算とは何か?

先に言った通り、あることが「できない」ことを主張するためには、それがどのような設定のもとで「できない」のかをきちんと表す必要があります。もちろん、逆に「できる」ことを主張する場合もそうあるべきですが、前回のように解がいきなり具体的に構成できてしまったような場合は、厳密な問題設定は後付けでも構わないということがあります。ところが、「できない」の場合はそのようなことは許されません。「どうやってもできない」ことを証明したいとすれば、その「どうやっても」の範囲を決めてやらないことには、そもそも話が始まらないのです。例えば、今回我々が問題にする通信量の下界の証明は、アリスとボブがテレパシーで会話できるとした場合には即座に破綻します。そんなことを言うと「非科学的だ」などとお叱りを受けるかもしれませんが、ここでの問題はテレパシーで可能なことを限定していないというだけで、それが実現可能(「科学的」とは言いません。)であるかどうかは全く別の問題です。*2テレパシーで何が可能であるかを数学的に規定してやれば、それを科学的な議論の中に含めることができます。もちろん、その問題設定が妥当であるかどうかはまた別の問題ですが。*3

というわけで、アリスとボブが「どうやっても大量の通信をしないとチェックできない」ということを議論するための枠組みをきちんと定めていきましょう。以下で示す枠組みは、通信複雑性の議論で用いられる一般的なものであり、この後にも様々な問題をその中で議論していきます。

まず、一番重要なことは、アリスとボブという2者の区別が存在することです。「アリス」とか「ボブ」というのはもちろんただのラベルであり、彼らが実際に何者であるかは問題ではありません。アリスとボブを分けたのは、もちろん彼らが情報を共有していないことを表すためであり、それ以上の意味はありません。問題は彼らが何を成すべきかであり、そのために何の情報が与えられ、そして、何の動作が可能であるか、それだけです。

一般的な枠組みを与えるために、次の抽象的なものを用意します。

  • 3つの有限集合 \mathcal{X}, \mathcal{Y}, \mathcal{Z}
  • 関数 f : \mathcal{X} \times \mathcal{Y} \to :\mathcal{Z}

関数 f : \mathcal{X} \times \mathcal{Y} \to \mathcal{Z}(x, y) \in \mathcal{X} \times \mathcal{Y} 成分の位置に f(x,y) を書いた行列で表されます。これを関数 f の表と呼ぶことにします。

これに対して、アリスとボブの目標と渡される情報は

  • 目標:f(x, y) の値を決定する。
  • アリス:入力として x \in \mathcal{X} を受け取る。最初の時点でボブの入力は知らない。
  • ボブ:入力として y \in \mathcal{Y} を受け取る。最初の時点でアリスの入力は知らない。

とします。

さて、このように目標を設定してやったとことで、次はアリスとボブにとって可能な動作を決めてやる必要があります。アリスとボブが「共鳴」してお互いの情報をコストなしで共有できるのであれば、上のような計算を行うことを考えるために、わざわざ2人を分ける意味がなくなってしまいます。ところで、今さらりと言った「コスト」こそが、「計算」を考える上での重要な部分です。何に対してコストがかかるのかを決めることは、計算の難しさを議論するための枠組みを決めることに直結します。今回の場合、コストがかかるのはもちろんアリスとボブの間の通信です。逆に、通信以外のことは考えない方が議論しやすいと思われます。そこで、アリスとボブは次のことができるとします。

  • アリス&ボブ:過去の通信履歴から一意に決められる順番に従い、0もしくは1を他方に送る。通信履歴とは、アリスとボブがそれぞれ送ったビット(0または1)の列である。
  • アリス:自分の入力 x と過去の通信履歴を見て、次に0もしくは1のどちらかを送るべきかを決め、ボブにそれを送る。
  • ボブ:自分の入力 y と過去の通信履歴を見て、次に0もしくは1のどちらかを送るべきかを決め、アリスにそれを送る。
  • アリス&ボブ:双方が過去の通信履歴を見て f(x,y) の値を知ったとき、その値を出力として通信を終了する。

これを見て分かる通り、アリスとボブが次に送るべきビットを決めるときの計算量については全く考慮していません。通信量に注目するために、余計なコストを勘定に入れなかったのです。今回我々は、「どうやっても通信量が多くなる」ことを証明したいのですから、「アリスとボブがどんな計算でも一瞬でできる」という仮定をおくことで結論が弱くなることはありません。アリスとボブが現実的に実行不可能な計算を行う神がかり的な能力を持っていたとしても、「どうやっても通信量が多くなる」ことを防ぐことはできないのです。

さっきからちらちらと「通信量」という言葉を使ってきていますが、これこそが我々が考慮すべき唯一のコストです。基本的には上で言った通信履歴のビット数のことです。ただし、「通信量」というだけでは複数の意味があります。それについては後で述べましょう。

上に並べたような、アリスとボブが関数値を計算するために行う一連のやり取りを「プロトコル(protocol)」と言います。単語の意味としては、「(複数の主体間での)取り決め」といったところで、外交関連でよく用いられる言葉です。また、ネットワークの世界でも、コンピュータ同士が様々な立場で情報をやり取りするために、数多くのプロトコルが定められています。もっとも、理論計算機科学の世界では、単に通信を主体とする手続きを指して「プロトコル」と呼ばせている(「アルゴリズム」と呼ばずに)ようです。

以上で登場人物は出揃いました。あとはこれを数学的にきちんと表すだけです。少し面倒なのはプロトコルの手続きを表すことくらいですかね。これには「遷移関数」というものを用います。定義の前に断っておくことは、\{0,1\}^\ast とは0と1を有限個(0個を含む。その場合は \epsilon (空列)となる。)連結した文字列の全体であり、文字列 s, t に対して st は連結を表すことです。

定義: 「決定性プロトコル」とは次のものの組である。ただし、\bot\mathcal{Z} には含まれない記号とする。

  • 3つの有限集合 \mathcal{X}, \mathcal{Y}, \mathcal{Z}
  • 選択関数: \mathrm{sel} : \{0,1\}^\ast \to \{\mathrm{A,B}\}
  • 遷移関数: \mathrm{A}: \mathcal{X} \times \{0,1\}^\ast \to \{0,1\}(アリス),\mathrm{B}: \mathcal{Y} \times \{0,1\}^\ast \to \{0,1\}(ボブ)
  • 出力関数: \mathrm{out}: \{0,1\}^\ast \to \mathcal{Z} \cup \{\bot\}

決定性プロトコルが入力 x \in \mathcal{X}, y \in \mathcal{Y} に対して行う計算とは、次の手順で進められるものである。すべての計算は有限ステップのうちに終了しなければならない。

  1. v \leftarrow \epsilon
  2. \mathrm{sel}(v)=\mathrm{A} ならば w \leftarrow \mathrm{A}(x, v)\mathrm{sel}(v)=\mathrm{B} ならば w \leftarrow \mathrm{B}(y, v)
  3. v \leftarrow vw
  4. \mathrm{out}(v) \neq \bot ならばその値を出力して終了。そうでなければ2に戻る。

ここで、v \in \{0,1\}^\ast を通信履歴という。特に、プロトコル \Pi の終了時の v\Pi(x, y) と書く。プロトコル \Pi の入力 x, y に対する出力値は \mathrm{out}(\Pi(x, y)) である。

定義: プロトコル \Pi が関数 f を計算するとは、すべての x \in \mathcal{X}, y \in \mathcal{Y} に対して \mathrm{out}(\Pi(x, y)) = f(x, y) が成り立つことを言う。

このプロトコルによる計算は、そのままでは分かりにくいでしょうから、視覚的に表現することを考えます。そのために「決定木」というものを用います。それは、遷移関数によって定まる通信履歴に応じて木の枝をたどっていくと、答えがある葉までたどり着けるというものです。

まず、通信履歴を木の頂点(節、葉)と見なします。すなわち、通信履歴 v \in \{0,1\}^* に対して、それに対応する頂点を同じ記号 v で表します。プロトコルの計算で現れない通信履歴は無視して構いません。(遷移関数などの値は何でもよいとします。)

頂点 v において、\mathrm{sel}(v)=\mathrm{A} ならば、そこに遷移関数 \mathrm{A}(x,v)x \in \mathcal{X} ごとの値を書きます。同様に、\mathrm{sel}(v)=\mathrm{B} ならば、そこに遷移関数 \mathrm{B}(y,v)y \in \mathcal{Y} ごとの値を書きます。そして、その下に遷移関数の値に従って進むべき枝を書きます。遷移関数の値0に対応する枝の先には頂点 v0 を、同1に対応する枝の先には頂点 v1 を書きます。

頂点 v において \mathrm{out}(v) \neq \bot となる場合は、\mathrm{out}(v) の値(プロトコルの出力値)を書いて、そこから下には続けません。すなわち、この頂点は葉となります。これは計算の終了時に対応します。

プロトコルの計算を見るときは、先にも言った通り、遷移関数に従って分岐していき、葉にたどり着いた時点での \mathrm{out}(v) の値を出力値とします。アリスとボブのどちらが次のビットを送信するかは、頂点に書かれた遷移関数で判定できます。

関数とそれを計算するプロトコルの決定木の例を図に示します。

f:id:azapen6:20130104033045j:plain

以上で通信による計算の話を終わります。

関数の通信複雑さ

再び通信量の話に戻ります。「通信量」をコストとして考えるといっても、ちゃんとした意味の候補はいくつもあり得ます。我々は特定のプロトコルの通信量を知りたいわけではなく、関数に対する通信量を知りたいので、定義は次のように少し複雑になります。

  • 特定のプロトコル \Pi によって、入力 x, y から計算を行うときの通信履歴 \Pi(x, y) のビット数:

|\Pi(x, y)|

  • 特定のプロトコル \Pi の通信履歴の長さの、すべての入力に対する最大値:

L(\Pi) := \max_{x, y} |\Pi(x, y)|

  • 関数 f を計算するプロトコルの中での、上記の L(\Pi) の最小値:

 D(f) := \min_{\Pi : \mathrm{computes} f} L(\Pi)

要するに、f を計算するプロトコルの中で最良のものの通信量(2番目の意味)をもって、関数 f の通信量と見なすわけです。2番目で最大値をとっているところを平均に置き換えると、また別の通信量が定義できますが、これを考えることの意味はあまりないことが判っているので、深入りはしません。一方で、最大値を最小値に置き換えることが無意味であることはご理解頂けるでしょうか?それはさておき、以上で定義された D(f) を今回の意味での通信量とします。

関数 f : \mathcal{X} \times \mathcal{Y} \to \mathcal{Z} に対して、上で定義される値 D(f) を「f の決定性通信複雑さ(deterministic communication complexity)」 といいます。今回はプロトコルが決定性なのでそのようになります。プロトコルが前回のようにランダムな選択(乱択)を利用する場合には、「乱択通信複雑さ」というものが(複数)定義されます。

次回示すべきこと

以上で設定が出揃ったところで、次回示すべきことを正確に述べます。対象としている関数は、アリスとボブのデータが等しいかどうかを判定するものでした。前回、アリスとボブはともに n ビットのデータをチェックするとしたので、アリスとボブの入力はそれぞれが持っているデータであり、入力の集合は \mathcal{X} = \mathcal{Y} = \{ 0, 1 \}^n となります。関数値は「等しい」ならば1、そうでないなら0を返すとすれば、\mathcal{Z} = \{ 0, 1 \} で良いでしょう。このとき、両者が計算する関数は、

f:id:azapen6:20121230001057p:plain

となります。EQは equality (等しい)の頭をとったものです。

我々が示すべきことは、「関数 \mathrm{EQ} を決定性プロトコルで計算しようとする限りは、どうやっても対象のデータをそのまま送信するのと通信量の意味で差をつけられない」こと、すなわち

D(\mathrm{EQ}) = n + 1

となります。上界の方はそのままで、アリスが全データをボブに送り、ボブが自分のものと比較して等しいかどうかを判断した結果を1ビットでアリスに返せば達成できます。

問題は下界の方です。これを証明するにはあるテクニックを使います。それは次回のお楽しみです。それでは、できるだけ早く次の記事を上げられるように頑張ります。

次の記事: http://azapen6.hatenablog.com/entry/2012/12/30/062358

*1:すなわちこれは、「加減乗除とべき乗根だけでは」一般解の式を得ることは不可能であると言わなければいけませんでした。実際、その意味の外では5次方程式の一般解の公式が存在します。

*2:計算複雑性理論では、現実的にありそうもない計算モデルが山のように出てきます。量子コンピュータというのも元来は空想の産物ですし、2012年現在で実用化にはまだまだ遠いようです。

*3:江戸時代の人から見れば、電気通信だってテレパシーと大して変わらないでしょう。現代では量子テレポーテーションという現象が知られていて、情報科学の世界でも研究が進められています。