イベント / EVENT

平成30年度 第6回 Q&A

第6回 2018年12月11日(火)

計算の理論と現実
-難しいはずの計算が実はいとも?簡単に-

岩田 陽一

講演当日に頂いたご質問への回答(全33件)

※回答が可能な質問のみ掲載しています。

多項式時間、指数時間は具体的にどのように使われているか。本講演の中での多項式時間の位置付け、指数時間の位置付け、どのように測定/算出するのか、の説明を具体的にお願いしたい。

どんな長さnの入力に対しても、T(n)という計算時間でアルゴリズムが動作することを証明できたとします。T(n)が多項式関数であればnに対する多項式時間、指数関数であれば指数時間と呼びます。アルゴリズムから自動的に導かれるものではなく、計算時間を証明する作業が必要になります。

帰着について再度説明をお願いいたします。

問題Aの入力を問題Bの入力に変換し、それに対する問題Bの答えを問題Aの答えに変換することが出来れば、問題Bに対するアルゴリズムを用いて問題Aを解くことが出来ます。この二種類の変換の組を「帰着」と呼びます。

「木っぽいグラフ」のアルゴリズムについて、最適化を証明できている事例をできるだけ説明してほしい。

木幅(木っぽさを測る指標の一つ)がwの場合に、頂点被覆と呼ばれるNP完全問題をO(2^w n)時間で解くことが出来ます。もしこれがO(1.99^w n)時間に改善出来ると、SETHと呼ばれる有名な仮説が崩れるため、最適であると信じられています。他にも、負閉路検出と呼ばれる問題はO(w m log n)時間で解くことが出来ますが、一般の(木っぽいとは限らない)グラフでの現在の最速な手法はO(nm)時間であり、w<=nが常に成立するため、ほぼ(log n倍を除いて)最適であると言えます。

計算可能性理論については定評のある教科書(のようなもの)をいくつか知っているのですが、計算複雑性理論についてはあまり知りません。どのような本が有名でしょうか。

専門書としては「Computational Complexity: A Modern Approach」 (著: Arora, Barak)が有名です。入門書としては「今度こそわかるP≠NP予想」 (著: 渡辺 治)などがあります。

計算複雑性の階層化に最近進展はあったのでしょうか。

階層のうち何々と何々が等しいというタイプの証明はあまり進展がありません。パラメータ化計算量のように、より細分する方向や、計算量の仮定から何かの不可能性を示す方向の研究が盛んです。私に近い分野ですと、多項式時間階層に関する仮定から、kernelizeと呼ばれる多項式時間圧縮の不可能性が示せるという発見などがありました。

「木っぽい」入力に対する計算量と一船の計算量について何らかの関係は知られているのでしょうか?(例えば、「木っぽい入力」に対しての計算量が0(f(n))のとき一船には0(g(f(n)))であるとか・・・

例えば、木幅という指標は高々頂点数以下であるので、木幅がwの問題がf(w,n)で解けるなら、一般の場合はf(n,n)で解くことが出来ます。

「木っぽいデモ」の分割赤点は容易に求められますか。求めるアルゴリズムはありますか。

はい、存在します。木は一点を取り除くと残りが半分以下になるような点が必ず存在し、そのような点を再帰的に線形時間で見つけていくアルゴリズムがあります。それを少し応用すると、木っぽいグラフに対しても適用できます。

特殊ケースでのアルゴリズムの論理化は、元々ある別のアルゴリズムを応用して生み出したものなのか、全く新しい閃きから創られているのか、どちらのケースが多いのかお聞きしたいです。

木の場合や平面グラフの場合のアルゴリズムの応用から生み出されるケースが多いです。また、それとは別に木っぽいグラフ用のテクニックも多数開発されており、それとの組合せで計算時間が削減されています。

暗号で使われるアルゴリズムはある「鍵」の情報の有無で計算量が大きく変わるようなものと思うのですが、その理解でよいでしょうか?そのとき「部分的な鍵」(手がかり)みたいなものがあって、計算量が段階的に小さくできるといった議論もありえるのでしょうか。

広く使われているRSA暗号などでは、解読に使う鍵(秘密鍵)と暗号化に使う鍵(公開鍵)のペアを作成し、公開鍵から秘密鍵を求める問題が難しい(多項式時間では出来なさそう)ということを利用して、秘密鍵の所有者だけが暗号を解読出来るという仕組みになっています。例えばnビットの秘密鍵の情報がn-kビット漏洩した場合を想定すると、残りの2^k通りを試すことで暗号解読が出来てしまいます。

先生はミレニアム懸賞問題にチャレンジされていますか?

たまたま別の問題を解いている中で良いアイデアが出れば嬉しいですが、狙って挑戦はしていません。

先生の実際のご研究では、いろんな問題のアルゴリズムを考えている?計算量の数式をいじっている?どんな場面なんでしょうか。?

他の論文を読んだりしている中で、こういうことが出来そう(アルゴリズムだったり、証明だったり)というアイデアのストックが何個かあって、ローテーションしながら細かい部分を考えて少しずつ進めるという感じです。

今現在、Googleやマピオン、ナビタイムのナビサービスで、どの程度用いられているものなのでしょうか。Googleと国産Webサービスでは、やはりこのような課題(最短経路算出)で、差がついているのでしょうか。

実際のサービスで使われている手法は公開されていませんが、もう少し経路に制約が入ったり、複数候補を出したいなどの要望から、計算時間を多少犠牲にした別のアプローチが取られているようです。最短路の研究をしていた著名な研究者がAppleやAmazonの研究所に転職された事例が多々あるので、こういった研究を重要視しているようには感じます。

計算理論を応用すると、解くのが難しい問題(暗号に使える?)を理論的に作ることができますか?

問題は今の所自動的には作れません。人間が作った問題の難しさを帰着で証明する形になります。難しい入力の生成などは、帰着を用いて、別の問題の入力から自動生成することは出来ます。

ハードを意識した高速/最適アルゴリズムはもう昔の話ですか?

応用分野では近年、メニーコア化・GPU・AIチップの登場で、ハードを意識した研究がより盛んになっています。理論分野ではハードウェアとして実現される遥か以前から研究がされており、更に将来を見据えた研究が進んでいます。

数値計算に適したプログラム言語はどのようなものがありますか。

数値計算ライブラリを使うユーザー側としては最近はpythonが流行っているように思います。ライブラリ開発側ではC++などが主流ではないかと思います。

現実の問題を解く場合、プログラミング能力が高い人は、直接プログラムを書いて、cut&tryでちゃちゃっとやる方が、理論的にあれこれ考えるよりも簡単に実用的なものができるように思います。個人的にはその方が楽しいですが、先生の場合はいかがでしょうか。理論と実践のバランスや、相互作用について考えをお聞かせください。

計算のボトルネックでない部分や、重要性の低い部分は、あれこれ考える必要はないと思います。一方で、超大規模計算をする場合や、性能の高い計算をする必要があり場合では、しっかりと理論を考える必要があります。

AIが進化することにより、AIそのものが最適なアルゴリズムを創り出すことはあり得るのでしょうか?

問題によっては効率的なアルゴリズムの自動生成などは可能であると思います。実際、すでに四色定理という有名な問題ではコンピュータによるアルゴリズムの自動生成・正しさの自動証明が行われています。ただ、一般にあらゆる問題でそれが可能かというと、非常に難しいと思います。

新しいアルゴリズムの発見と特許との関係は?

基礎研究で研究されているような汎用的なアルゴリズム設計技法が特許に結びつくことは少ないです。一方で、具体的な応用があり、それに特化したアルゴリズムなどは特許が取られることもあります。

新しいアルゴリズムを発見したときはどのような気分になりますか?

先人の積み重ねの上で新たな発見をすることを指す「巨人の肩の上に立つ」という素敵な言葉があります。新しい発見が出来たときは、これまで誰も出来なかったことを成し遂げた達成感と共に、巨人の一部となれた喜びを感じます。

効率の良い計算には、結局は特殊な例についての計算法をしらみつぶしに探す他ないのか。

現実の計算を効率化する場合には、入力にどんな特徴があって、それをどう活用出来るかを考えることになります。その特徴の例や、特徴の活用法に関するテクニックを積み重ねていくことで、別のケースにも応用出来るようにすることが基礎研究にあたります。

この分野は盛り上がっているか、また若い研究者はどれだけいるか、日本や他の国では盛り上がっているか。

FPTアルゴリズムの分野は欧州を中心に盛り上がっています。研究者は20代・30代の若手が大半です。理論分野は他の分野に比べると日本の研究者は少ないように感じます。

量子コンピュータは「総当たり」に強いと言われていますが、効率化のアルゴリズムで助けてやれば、「より高速に」解けるのでしょうか?あるいは、量子コンピュータには効率化アルゴリズムは余計なお世話?

量子コンピュータでも効率化は重要です。総当たりでO(2^n)時間がかかるものを、量子コンピュータを用いるとO(2^{n/2})時間にするアルゴリズムが存在します。賢いアルゴリズムを使うと、例えば、総当たりより高速なO(1.5^n)時間のアルゴリズムを作ることが出来、これを量子の場合にも応用してO(1.5^{n/2})時間に改善出来るケースがあることが知られています。

Quantum Computerにおけるアルゴリズムは、今までのアルゴリズムと異なるものになる事があるのでしょうか?

量子を用いることで古典コンピュータの限界を超えるには、今までのアルゴリズムとは別のものを開発する必要があります。量子コンピュータが実用化されても、あらゆる計算がそのまま速くなるというわけではありません。

量子コンピューターによってNP困難問題が解けるようになるでしょうか?

量子コンピュータでもNP困難問題は多項式時間では解けないだろうと多くの研究者に信じられています。一方で、現在広く使われているRSA暗号はNP完全ではなく、量子コンピュータによって多項式時間で解読出来てしまうことが知られています。

計算量理論と量子理論(量子コンピュータ)は相互に影響し合うものでしょうか。

はい、非常に密接に関係しています。例えば最近の大きな進展としては、量子計算のQIPという計算量クラスと、古典計算のPSPACEという計算量クラスが実は等価であるという証明があります。

帰着の選び方がセンス?

帰着を実際に作る作業はパズルゲームのような感じです。

AIが作り出せる?自動化?理論とプログラミングのバランス?

問題によっては効率的なアルゴリズムの自動生成などは可能であると思います。実際、すでに四色定理という有名な問題ではコンピュータによるアルゴリズムの自動生成・正しさの自動証明が行われています。ただ、一般にあらゆる問題でそれが可能かというと、非常に難しいと思います。

アプリケーションで使われているのはこのようなもの?スピードに差がある?Google等で使われている?わかっているのか?

企業で使われている手法については公開されていませんが、最短路研究の著名な研究者が企業の研究所へ移るケースもあり、こういった研究が活用されているのだと思います。

ハードを意識することはある?面白い問題とは?

私は今の所ハードは意識せずに研究しています。

普段はどういうふうに問題を考えている?コンピュータ?手と紙?どんな気分になる?

理論研究をしているときは、紙とペンで考えることが多く、たまに実際にプログラムを書いてチェックをするという感じです。

公開かぎ暗号方式と今回のお話は何か関係があるのでしょうか?

広く使われているRSA暗号などでは、解読に使う鍵(秘密鍵)と暗号化に使う鍵(公開鍵)のペアを作成し、公開鍵から秘密鍵を求める問題が難しい(多項式時間では出来なさそう)ということを利用して、秘密鍵の所有者だけが暗号を解読出来るという仕組みになっています。

岩田さんは、「数学」で苦手、納得できない分野はありますか?

数学といっても幅が広いですが、離散なものに比べると連続なものはあまり得意ではないです。

筆算のように、低速だが簡単で「人間向き」のアルゴリズムがあると知りました。最近、コンピュータ将棋が強くなり、名人に勝つこともある程ですが、コンピュータの計算方法は複雑であるため、人間ではマネできない(序盤でコンピュータが指した手をマネすることはできるけど)ということが何となく感じられました。コンピュータのマネをしても応用できない・・・人には人に合ったアルゴリズムが必要ですね。

はい。一方で、人間にも理解できるアルゴリズムの重要性も機械学習分野などを中心に高まっており、コンピュータの判断をどう説明するかといった研究も盛んになっています。

shimin 2018-qa_6 page3469

注目コンテンツ / SPECIAL