管理人の部屋

「紅い数学科」

どうも，旧サイト閉鎖に伴い，囲碁部HPの一新を担当した「自称：紅い数学科」です．勝手ながら，初代管理人として挨拶させていただきます．このページは各代の管理人が自由気ままに自己紹介する場です．

難しいって？

　キミたちは夜空を彩る星の輝きに心を奪われたことがあるだろう．ひとつ，またひとつ，その星々を数え途方もない数に驚いてしまったかもしれない．否，うまく数えられなくて，そのように諦めてしまっただけかもしれない．ところで，2, 3, 5, 7, 11, ……のような素数と呼ばれる数は数の素です．皆さんもご存知の通り，あらゆる自然数は素数の積で現すことができるからです．

以下の自然数を素因数分解せよ

なんて，問題に見覚えがあるだろう？　中学生でも知っている単純な数学の問題だ．キミたちも「なんて，面倒な問題だ」とか，「難しいなぁ」とか思ったことだろう．実際，その感覚は正しい．因数分解は難しいという考えが，現代の暗号をつくるのに都合がよいとされている．ところで，“難しい”とは何か，聡明なキミたちなら疑問に思うだろうし，既にご存知のことだろう．

さて，キミたちが問題を“難しい”と感じるとき，当然ながらその問題は“解ける”という前提に立っているはずだ．そもそも，解けない問題なんてクソゲーだからな．それはともかくとして，キミたちはお気付きだろうか．『問題が解ける』ということは，言い換えると『アルゴリズムが存在する』ということ．つまり，“難しい”を考えるということは，“アルゴリズム”を考えるといっても差し支えないだろう．

1936年，Alonzo ChurchとAlan Turingが独立にアルゴリズムの定義が導入された．彼らの定義は等価であり，アルゴリズムの概念はChurch-Turingのテーゼと呼ばれている．以来，アルゴリズムの定義にはTuring machineを用いるのが一般的である．

話は逸れただろうか．いや，そんなことはない．ところで，キミたちは“難しい”という基準をどのように考えるだろうか．これに関しては，“簡単な”問題を念頭に置いて考えてみると良いだろう．

計算せよ
(1) 3*4+7*2
(2) 19*95+407*155

上記の単純な計算問題を例に考えてみよう．キミたちは，(1)より(2)の方が“難しい”と感じるに違いない．しかしながら，この２つの問題は本質的には全く同じ問題である．つまり，この２つの問題は“難しさ”は同じであると考えるのが妥当だ．では，何を基準に“難しい”を定めれば良いのだろうか．このとき，登場するのがTuring machineである．Turing machineとは，端的に言えば，我々が行う“計算”を実に巧妙な手法で数学的に定式化したものである．

想像して欲しい，我々が“計算”を行うとき何が必要だろうか．当然ながら，紙とペン，そして解くべき計算問題（instance）が必要なことは言うまでもない．だが，それだけで計算ができるだろうか．普段キミたちは意識しないかもしれないが，計算規則がなければ計算を行うことはできない．Turing machineにおける紙は1次元のテープであり，1回の処理でペンに相当するヘッドが読み出し，書き込み，左右への移動を行う．コンピュータがメモリにデータを読み書きするところをイメージすればよいだろう．

さて，問題が解き終えたとき，キミたちはペンを置くだろう．これをTuring machineに置き換えると，動作が停止することに相当する．直感的に，“難しい”問題を解くとき時間がかかるだろう．つまり，Turing machineが計算を始めてから停止するまでの時間が長くなる．ここでいう『時間』とは，処理の回数と置き換えてよい．すなわち，“難しい”問題であればあるほど処理の回数が多くなる．ところが，先ほどの例題に戻ってみよう．同じ問題であっても，数字が大きい（入力サイズが大きい）計算問題であればあるほど，計算時間が多くなるのは必然である．したがって，問題の“難しさ”は『入力の大きさに対する計算時間の長さ』で捉える．これがいわゆる，計算量の概念である．

一般に入力サイズNに対して，計算時間がnに関する多項式（N^2やN^10など）で抑えられる問題は“簡単”といわれており，多項式時間で抑えられない問題，あるいは抑えられるかどうか分かっていない問題のことを“難しい”という．つまり，冒頭で挙げた因数分解が“難しい”という意味は，自然数を素因数分解する効率的（与えられた自然数の桁数に関する多項式時間でできる）計算手法が知られていない，ということである．

ミレニアム懸賞問題のひとつに『P vs NP 予想』がある．これは計算の“難しさ”に関するギャップを探る問題である．決定性Turing machine（上記で説明したもの）と非決定性Turing machineに関して，多項式時間で解ける問題の範囲に差があるのかを問うている．多くの研究者がP ≠ NPを予想しているが，真相は明らかにされていない．ところで，厳密にいえば素因数分解をP vs NPの枠組みで語ることは間違いである（関連がないというわけではない）．P vs NPとはあくまで言語（判定問題）に関する話であり，素因数分解は解を求める問題（探索問題）で議論されるべきである．

探索問題に関する計算量理論は，とても興味深い話題である．我々が日常的に見かける問題は，この枠組みで議論され，いくつかの問題に関しては完全であることが知られている．例えば，ゲーム理論を学んだ人なら親しみのあるNash均衡を求める複雑さはPPADという探索問題の計算量Classに関して完全問題であることが知られている．

長々と語り続けたが，探索問題の複雑さは私のもっとも興味をそそられる話題である．キミも計算量理論の深淵をのぞき，心躍るような勉強や研究の日々に青春を捧げてみませんか．そして，この記事を最後まで読み通したキミは間違いなく，囲碁人の素質を持っています．キミが九大囲碁部に来る日を待っています．

参考文献