マルレク「エンタングルする認識」ダイジェスト #2

【「全能者」との対話で得られる認識 -- Interactive Proof 】

なんか怪しいタイトルですね。
怪しいついでに、もう一つ怪しい話を。

今から見ればだいぶ前になりますが、「AI=人工知能」の大ブレイクが起きたとき、盛んに使われたのが「シンギュラリティ」という言葉です。機械の知能が人間の知能を超える時がいつか来る。それをこの言葉で呼んでいたように思います。

ただ、この言葉やその意味に、僕はいささか「怪しさ」を感じていました。なにが人間の知能の限界であるのか？　また、シンギュラリティの到来は、機械の知能が人間の知能をどのように超えることを意味しているのか？　当時流行した議論では、そうした基本的なことが、あまりよく考えられていないように感じました。

こうした問題を徹底的に考えるのは意味があることだと、僕は考えています。冒頭のタイトルの「全能者」は、いわば、機械の「シンギュラリティ」をはるかに超えた能力の持ち主です。ただし、「対話型証明 Interactive Proof」に登場する架空の存在です。

「対話型証明 Interactive Proof」というのは、こうした「全能者」と普通の人間が「対話」をしたときに、何が分かるかを考えようという枠組みです。

アーサー王伝説では、アーサーに仕えるマーリンという魔法使いが出てくるのですが、「対話型証明 Interactive Proof」では、「全能者」をマーリン、「全能者」と対話する普通の人間をアーサーと呼ぶことがあります。

アーサー王伝説のマーリンは、魔法使いですので、火を吹く竜を召喚したり、人間を豚に変えたり、文字通りなんでも出来るのですが、Interactive Proofのマーリンは、そういう魔法を使えるわけではありません。

ただ、理論的・数学的能力においては、彼は「全能」です。もし、リーマン予想が正しいのなら、彼はそれを瞬時に証明できます。もちろん、「全能」と言っても、数学的に証明不可能な 1+1=3 を証明できるわけではありません。

Interactive Proofの枠組みでは、「全能者マーリン」を「証明者 Prover」と呼ぶことがあります。彼は、全知全能で、どんな問題も瞬時に答えを返す能力をもっています。ただし、ここが重要なのですが、彼は誠実ではなく、時々、人を欺く嘘をつきます。

一方の「普通の人アーサー」を、Interactive Proofの枠組みでは、「検証者 Verifier」と呼びます。彼は、理性をもっていて、「全能の証明者」の主張を「検証」しようとします。彼は、「全能の証明者」の言うことを、盲信はしません。

Interactive Proof Systemというのは、この両者が対話を繰り返すことで、何かを証明しようというシステムです。

基本的には、検証者が証明者の主張を受け入れた時、すなわち、証明者が証明者の主張が正しいと検証者を納得させることができた時、証明は終わります。ただし、ある場合には、証明者の検証者の説得は失敗し、検証者は証明者の主張を拒否して、証明が終わります。

こんなんで、何か役に立つのかと思われるかもしれません。ここでは一つだけ例をあげます。

n個の頂点を持つ二つのグラフGとHがあったとします。この二つのグラフが同じものであることを証明する問題を「グラフの同型問題」といいます。この問題は、複雑性のクラスNPに属します。

ところが、二つのグラフが同じものではないことを証明する「グラフの非同型問題」は、実は、「グラフの同型問題」より難しい問題であること、すなわちその複雑性クラスはNPを超えるものであることが、Interactive Proofの手法を使って初めて証明されたのです。

このあたりの詳細は、ここでは述べませんが、興味ある方は丸山の資料「Interactive Proofの発展」https://www.marulabo.net/docs/ip-complexity/　をチェックください。

この例は、数学的な議論ですが、セミナーでは、「全能者」と「人間」の対話という、一見奇妙な想定が、人間の多様な認識活動の強力なモデルを提供することを、いくつかの例でお話したいと思います。

過去・現在・未来