複雑系セミナー - 　森の生活　

1999年9月10日 14:00 北大理学部4号館508室
竹内泉（京都大学情報工学教室）
自己相似図形の計算量
Abstract:
　本発表では、多項式時間計算可能な線型函数で定義される数直線
上の自己相似図形であり、計算量が非決定性多項式時間完全である
ような図形を構成する。
　最近、河邑紀子らによって、計算可能性という面から視た際の自
己相似図形の複雑さはどのようなものであるか、という問題提起が
なされた。
　一方、計算可能性解析学の中では実数の計算可能性、実函数の計
算可能性が定義されていた。バイハラーフはそれを応用して、閉集
合に対する計算可能性を研究した。そこで云われている計算可能性
に基いて、閉集合の計算量を測ることが出来る。ここではこの計算
量を用いる。
　既に鴨らによって、「多項式時間計算可能な縮小写像から生成さ
れる自己相似図形で、多項式時間開集合被覆条件を充すものは、多
項式時間計算可能であること」「多項式時間計算可能な縮小写像か
ら生成される自己相似図形は、非決定性多項式時間計算可能である
こと」が得られていた。この結果、多項式時間開集合被覆条件を充
さない自己相似集合で、計算量が多項式時間計算可能を超えるもの
が存在するかどうかが、未解決問題として残されていた。
　本発表では、この問題を解決し「多項式時間計算可能な縮小写像
から生成される自己相似図形で、開集合被覆条件を充さず、図形と
しての計算量が非決定性多項式時間完全であるものが存在すること」
を証明した。

複雑さの起源を問う
　　　
時田恵一郎サイバーメディアセンター助教授
大規模計算科学研究部門
唐突ですが、クイズをひとつ。３と４と７と８を一回ずつ使って四則演算だけで答が１０になる式を作りなさい。かっこを使ってもよろしい。これは、筆者が子供の頃父親と車で出かけるときによくやった遊びである。前を走る車のナンバーを使ってどちらが先に答を出すか競うのだ。例えば、１２３４なら、（３×４−２）×１＝１０など。読者のお楽しみのために答はこの文章の最後に明かすことにするが、ここでは「３４７８」は最も「難しい」例題のひとつであるということだけ述べておこう。さてこの問題を「ナンバープレート（ＮＰ）問題」と勝手に呼ぶことにする。「ＮＰ問題」には答がない場合もあり、例えば我が家の愛車のナンバー（８８００）の場合に答がないことは「簡単」にわかる。

　ここで、「ＮＰ問題」を拡張した、「与えられた任意のＮ個の整数を一回ずつ使って四則演算だけで答が整数Ｍになる式を作ることが可能か」という問題を「拡張ＮＰ問題」と勝手に呼ぶことにしよう。実はこの問題は、最初にあげた例のように一桁の整数４個（Ｎ＝４）でも「難しい」場合があるのだが、Ｎがある程度大きくなるともはや地球上に存在するどんなに高速なコンピュータでも解くことができなくなってしまう。Ｎの増大とともに、可能な式の数が指数関数的に増えてしまい、計算時間が急激に増大するからである。このような問題を計算理論の分野でもＮＰ完全問題と呼ぶ（というかこっちが本家^^;）。ここでのＮＰはNondeterministic Polynomial-time solvableの意味で、一般に問題の規模Ｎの多項式で表される計算時間では解くことができないと信じられている問題のクラスを指す(1)。

ＮＰ完全問題の中でも最も有名なものの一つに、「巡回セールスマン問題(Traveling Salesman Problem:TSP)」がある。これは、例えば地図上のＮ個の都市を一回ずつ訪問して元の場所に戻るような経路のうち最短のものを探せ、という問題である。この問題も都市数Ｎが大きくなると計算量の爆発が起こってしまい、コンピュータでも調べ尽くすことができない。現在厳密な最短経路(最適解)が知られている最大規模の例題は（Ｎ＝）1万3509都市の場合で、1998年に並列計算機を用いて、のべ４年分のＣＰＵ時間をかけて求めたということになっている(2)。「一人のセールスマンが何万都市も営業して回るなんてことはないんだから、そんな問題考えなくたっていいだろう？」という疑問はもっともだが、実はＴＳＰ以外にも応用上大変重要な数多くのＮＰ完全問題(3)が知られていて、それらすべてが相互に還元可能であり、計算量の観点からは本質的に等価な問題であることが知られている(4)。つまり、どれか一つでもいいからＮＰ完全問題を多項式時間で解くアルゴリズムを考え出すことができたら、全てのＮＰ完全問題が多項式時間で解けたことになるのだ。仮に特許を取ることができたらビル・ゲイツなど足元にも及ばない大金持ちになることが可能であろう。

　しかし、その夢はほぼ絶望視されている。これまで世界中の専門家たちが挑戦し続けてきたが、ＮＰ完全問題を多項式時間で解くアルゴリズムは一つも発見されていないからである。とはいえ、「ＮＰ完全問題は多項式時間で解けない」ということが証明されているわけでもないのである。実はその証明は現代数学において最も難しい問題の一つとして知られており、１００万ドルの懸賞金がかかっているほどである(5)。「ＮＰ完全問題は多項式時間では解くことができないと信じられている」と書いたのは、状況証拠しかないという現状を表現したものなのである。
ところで、同じＮＰ完全問題でも例題毎にその「難易度」が大きく変わることに注意しよう。ナンバープレート問題でも、３４７８は「難しい」けれど、８８００は「簡単」に思える。ＴＳＰだって、たとえ何百万都市の場合を考えたとしても、全ての都市が一直線上に並んでいたり、一つの円の上に並んでいたりしたら解は自明である。ある問題がＮＰ完全問題であるという場合は、いくつも考えられる例題のうち最も「難しい」ものを想定しているわけで、ＮＰ完全問題だからといって全ての例題が「難しい」わけではない。

　さて、ここまで「難しい」とか「簡単」とかいう言葉を無造作に使用してきたが、ある例題が一つ与えられたときに、そもそも何を基準にそれが「難しい」だとか「簡単」だとか言うことができるのだろうか？

　　実は、これはある問題の属するクラスがＮＰだとかＰ（多項式時間で解けるような比較的「簡単な」問題）だとか分類する以上の難問、というか本質的には解けない問題なのである。「難しさ」の定量的な定義として、例えば、「Ｋｏｌｍｏｇｏｒｏｖ-Ｃｈａｉｔｉｎの複雑さ(ＫＣ-ｃｏｍｐｌｅｘｉｔｙ)」と呼ばれる量を考えてみよう。これは、ある情報を表現（生成）するのに必要な「表現（プログラム）の長さ」をもってその情報の「複雑さ」の指標とする、というものである。例えば、ＫＹＯＮＫＹＯＮＫＹＯＮ...ＫＹＯＮ(400文字) （＝「第１００代目小泉今日子」）(^^;)は(ＫＹＯＮ)100(=10文字) と書けるのでＫＣ-ｃｏｍｐｌｅｘｉｔｙは１０で、一方「寿限無寿限無五劫の・・・」は１０５文字あるらしいが、ところどころ繰り返しがあるものの、あまり圧縮できないのでＫＣ-ｃｏｍｐｌｅｘｉｔｙはかなり長いまま、である。つまり、「第１００代目小泉今日子」よりも「寿限無・・・」の方がＫＣ-ｃｏｍｐｌｅｘｉｔｙが高く、より「複雑」だということになる。

そこで、あるＮＰ完全問題の例題の解を求める手続きのＫＣ-ｃｏｍｐｌｅｘｉｔｙをその例題の「難易度」と定義しよう。先ほどあげた直線状に都市が並ぶＴＳＰの例題は、「直線」と漢字二文字で解を表現できるから、「難易度」最低といえるだろう。さて、問題は、実用上問題となるような、人間が見て「難しそうな」問題に対してＫＣ-ｃｏｍｐｌｅｘｉｔｙを一般的に求める方法があるか、である。これができれば、ある例題に対しては「これはＫＣ-ｃｏｍｐｌｅｘｉｔｙが非常に高いから計算機で厳密解を求めるのはあきらめて近似解で我慢しよう」とか、別の例題に対しては「これはＫＣ-ｃｏｍｐｌｅｘｉｔｙが低いから計算機で解けそうだ」とかあらかじめ当たりをつけることができてハッピーである。ところが、すでに述べたように、一般にＫＣ-ｃｏｍｐｌｅｘｉｔｙを決定するアルゴリズムは存在しないことが知られているのである！

　つまり、「なんとなく難しい」ことはわかっても、「どれくらい難しいか」をあらかじめ知る手立てはなく、実際に解いてみなければ「難しさ」はわからないし、しかも「難しさ」はどれだけ計算しても確定しないかもしれないのだ(6)。言い換えると、ＮＰ完全問題のような難しい問題においては、各例題毎に難易度が異なり、各例題の「個別性」を無視することができない。にもかかわらず、「個々の難易度」を量る一般的なモノサシが存在しないのである。

これは、対象の振舞いを「平均」や「ゆらぎ」などに縮約して「普遍的な振舞い」を見出すことにより理解する（ことに慣れている）筆者のような物理出身者にとっては困った情況である。ある自然の振る舞いを記述する際の、理論科学の目標は、まさにＫＣ-ｃｏｍｐｌｅｘｉｔｙの低い解を探すこと(7)であるが、それは、あらゆる例題に共通する普遍的な性質が、任意の一つの例題の本質をも語り尽くしている(8)、という前提に従っているからである。しかし、上で示したようなNP完全問題における興味は、例題一つ一つの解にあるのであって、すべての例題に対する「解の平均」等ではないのである。実際、統計力学の手法を使ってランダムに都市が散らばった場合のＴＳＰの可能な全例題の解の平均（最短巡回距離の平均）を見積もることは可能であるが、その知識が与えられた任意の一つの例題の解を求めるために必ずしも役立つわけではない。また、アメリカにある１３，５０９都市の最短巡回経路が求まったからといって、その解を用いて日本の１３，５０９市町村の最短巡回経路を「類推」することもまた不可能なのである。世の中には目もくらむほどの数の「複雑系」の本が溢れていて(9)、いろんな人がいろんなことを言っているが、個人的には「複雑系」とはこの「個別性」を無視できない現象を指すと言ってもよいのではないかと思う。話はややそれるが、複雑系研究に対する批判の一つに、「理論科学の王道である法則の探求を放棄してしまっている」というものがあるが、それは「各論」だとか「個別性」といったものを切り捨てることができないという状況と無縁ではないだろう（博物学的な「網羅的各論」が法則を浮かび上がらせることもあるのではないかと個人的には思ったりもするのだが）。
ところで、いわゆる「複雑さ」と「煩雑さ(込み入っていること)」を混同しているように思えるかもしれない。しばしば「複雑さ」と「煩雑さ」の違いが強調されてきた。「非常に込み入った関係で結ばれてはいるが、うまく解きほぐせば複数の単純な部分系に分解することが可能で、その部分系のメカニズムを孤立系として理解することにより、その総和として全体のメカニズムを理解することができる」のが「煩雑系（込み入った系）」であり、「どんな部分系の切り出し方をしても、孤立系として理解することはできず、総和としての全系の振舞いが、部分系の振舞いに影響を与えてしまい、それが逆に全系の振舞いに自己言及的に影響する」のが「複雑系」であるとされる。コンピュータが解くことのできるＮＰ完全問題の例題は、線形計画法や枝刈りを用いて問題を分割して解くことができるから「煩雑系」であって、「複雑系」ではないのではないか。このような疑問に対しては、部分系への分割可能性を問題の規模に依存しないものとして定義する、と答えることにしよう。この意味では、物理の教科書に出てくるような、例えば平均場近似が厳密であるような問題は「煩雑系」であって「複雑系」ではない。なぜなら、問題の規模が無限大の極限（熱力学的極限）でなお分割が可能（separable）なのであり、それが平均やゆらぎといったKC-complexityの低い解を用いた現象の説明を可能にしているからである。「煩雑系」においては、非常に規模の大きい問題でも分割可能であることが、各例題の「個別性」の消滅をもたらすのである。
ＮＰ完全問題に関して「難しさ」を「複雑さ」と同一視してきた。これは、我々があるものを複雑であると思うのは、「わかり難い」からであり、「得難い」情報を含んでいたり、「得難い」状態を実現しているからである、という素朴な感覚によるもので、特にそれ以上の根拠があるわけでもないので、同意しない人もいるかも知れない。しかし、ここではあえて筆者は上記の意味でＮＰ完全問題を「複雑系」と呼ぶことにする。ではＮＰ完全問題の場合、その「複雑さ」は何がもたらしているのだろうか。ＮＰ完全問題における問題の「要素」は、単なる都市の位置を表す点の集合である。すでに述べたように点がまっすぐに並んでいたら答えは自明なので、ある例題を複雑にしているのは、各都市の位置「関係」である。この位置関係が、ＴＳＰの各例題を難しくしたり、簡単にしたりしているということは、すでに述べた通りである。つまり、個々の要素が単純であるにもかかわらず、ある種の多様性が生み出され、個別性が問題になるのは、要素間の関係、すなわち「相互作用」の組み合わせが多様で複雑だからだ。「複雑さ」も「難しさ」も、全ては「相互作用」が生み出す魔術なのである。ＮＰ完全問題を解く試み(10)は、この魔術を解く試みなのだ。
ここで、そのような「魔術的な難問」が目の前で解かれるのを見たとすると、我々はそれこそまさに魔術だと思ってしまうことだろう（魔術には魔術で対抗するしかない）。実際、ダーウィンが１８５９年に「種の起源」を著すまでは、人類はこの世の全ての複雑さを神という名の魔術師の仕業だと思っていた(11)。ここでの「魔術的な難問」とは我々自身を含む多様な生物の存在理由である。生物を形作るメカニズムはあまりにも複雑なので、いまだに地動説を信じない人よりもダーウィニズムを受け入れない人の数は圧倒的に多いものと思われる。たしかに生命が地球に誕生し、多様で複雑な生物へと進化したことは、ＮＰ完全問題を解くように、実現することが途方もなく難しいことのように思われる(12)。しかし、自然はまさに魔術的にデザインされて、我々の目の前に実在している。どのように解かれたのかはまだよくわからないが、我々のまわりは自然という名の「魔術的な難問」の解答例で満ち溢れているのである(13)。遺伝子発現の多様性、蛋白質の多様性、免疫系の多様性、熱帯雨林や珊瑚礁などの生態系における種の多様性を生み出しているものは何か。この「魔術的な難問」すなわち「複雑さの起源の謎」を解く鍵は、やはり多様で複雑な相互作用である。この場合にも、物理化学系ではあまり見られないような、あらゆる要素間に作用する相互作用が、問題の規模によらない分割を不可能にしている。生命の諸問題が「複雑系」の問題なのは、その複雑さの起源が明らかでないからであり、それを孤立系に分解して理解する「煩雑系」では有効だった方法がほとんどの場合に使えないからである。
さて、紙数が尽きてきたようだ。ＮＰ完全問題を例にとって、複雑さの問題から始めて強引にダーウィニズムにまで持ってきてしまった。かなり舌足らずではあったけれど、言いたかったことは、「複雑系」と呼ばれる対象の研究には二つのアプローチがあるのではないか、ということだ。一つは、ＮＰ完全問題などの数学的・工学的な要請に基づく複雑系研究であり、これは複雑な問題をどう解くか（どのように低いKC-complexityの解を得て、理解したり操作したりするか）というものである。一方、自然科学としての複雑系研究は、魔術的にデザインされているもの、言い換えればいかにもＮＰ完全問題を解いているかのように見える、一見途方もないことを実現している自然の振舞いの起源を解明すること、であるといえる。前者は複雑な問題を解く方法を演繹的に解明することであり、後者は複雑な問題を解いているように見えるものを帰納的に理解することに対応している。また、前者は、複雑なものを比較的単純な、人工的な問題設定の側から、後者は自然が示している解答例の側から解明していくことに対応しているとも言えるだろう。R. Dawkinsは「複雑なもののふるまいは、秩序だった階層構造をなす連続した層とみなされる各構成部分間の相互作用にもとづいて説明されるべきだと、われわれは結論した。しかしもう一つの問いは、複雑なものが最初はどのようにして存在するにいたったのかというものである。」と書いている(14)。相互作用と複雑さとの関係については多くの人が言及しているが、上で述べたような複雑系研究における後者の側面、すなわち魔術的にデザインされているものの複雑さの起源の問題についてはあまり指摘がないように思える（意識的に取り上げられていないだけなのかも知れないが）。これは、よくいわれる、「科学はHOW（原因と結果を結ぶプロセスの定式化）を問うもので、WHY (原因そのもの)を問うものではない」ということとも無関係ではないだろう。科学の歴史は「WHY」を説明すると称する安易な合目的的なこじつけとの戦いの歴史でもあるので、「目的論」に対しては強いトラウマがあるのだ(15)。しかし、魔術的にデザインされているものの起源を問うならば、結局は目的論を避けては通れないと思う。問題は、目的論のもつ危うさを自覚しつつ、それをどのようにして科学の俎上にのせるか、であろう。これについては筆者も今のところ特に明確な方針を持っているわけではないのだが、現在我々が、「複雑系」という言葉が５０年後に残っているかどうかに関わる重要な分岐点に立っていることだけは確かなのではないだろうか。

　（ナンバープレート「３４７８」問題の答）（３−７÷４）×８＝１０。コンピュータでしらみつぶしに調べてみると、可能な式が１万通り以上もあるのに対して、答はこの一つだけであることがわかる。一度分数になって整数に戻るところが人間には難しく感じられるのだろうか。ちなみに例題「１２３４」の解は１３１個もある。「解の個数」も「難しさ」の指標の一つになるだろう。