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

出来るだけ寝ていたい

1日最低12時間睡眠、寝たら負け

P≠NP問題

まあ、通常情報系の勉強をしに大学に行っている人間は誰でも知ってはいるであろう(知らない人は大学やめた方が良いかもしれない)この有名なミレニアム懸賞問題

私の場合、この問題自体は中学の頃に適当にパソコンで「ミレニアム懸賞問題」と検索したところ偶然にもそのリストの中に「P≠NP」という全く何を言っているか教える気もない様な面をした問題があるなぁなんて感じてスルーしたのが初対面だったかと。

高校の時は妄想でPは確率、Nは整数かな!なんて思って放ったらかしにしました。駄目な子ですね。せめてもう少し調べれば良かった…。

大学に入る前に友達と本屋に行って「専門外の知識の概要や面白さをある種の教養として知っておきたいね。どんな本が良いのだろう。こう、数式が沢山ある定量的で参考書の様な本よりか定性的な感覚で大まかに理解できる本は中々見つからないね。」と喋っていたらBLUE BACKSなる良い本たちを紹介してくれた。
ざっと本棚に積まれたBLUE BACKSを眺めると確かに一般大衆向け。
「なるほど。自分の友人には博識な人が山ほどいるが彼らはこういう本を片っ端から読んだのか。流石だなぁ。」なんて思いながら見つめていた。
すると友人が一冊手に取って僕に見せてくれた。題名は『「P≠NP」問題』と書いてある。
見たことのある問題だけど何で僕に見せた?と思っていると彼は「これは君に絶対に必要な類の話題。だって情報系の人間だろ?それに君は数学も大好きなんだから。」と言われ驚いた。
こいつがまさか僕の専門内なのか……??
渋々見てみると本当にコンピュータの事が書いてあった。第一印象とはまるで違った。
友人は「専門内の内容なら知っておけ。他の情報系の人間に馬鹿にされるぞ。自分の専門内の事かどうかもわからない人間は大学に来なくていい。」と言い「確かにそれは嫌だな。ごもっとも」と思い買った。(危ない危ない。ギリギリ大学入学前だからセーフ)

いざ読む。新書は読みにくいが専門書よりマシ。
優しく書かれていたがどうもピンと来ない。
あーわかってないなぁ。と思い諦める。
これは一年後に読もう。そして今はこの様な問題がこれから自分が学ぶ内容の中に潜んでいるという事実だけを覚えて先に進もうと約束した。

一年経ったから読んだ。
前半はえらく簡単な内容になってる。
中盤もえらく簡単な内容になってる。
後半もまあわかった。
感動したね。一年でここまで自分の脳みそは成長したと思うと。
これが専門内っていうことなのか、と。
まぁ大体大学で習った事の復習レベル。
計算量という概念に関しては自分はアルゴリズムに興味があって独学である程度勉強していたのですんなり頭には入った。問題無かった。それに計算量と言ってもO記法とΩ記法、Θ記法を知っていれば良いだけなのでこの程度なら情報系なら知ってて当然の類。
Pが何を表し、NPが何を表すのかもしっかりと把握した。(確率と整数じゃ無かった。)
決定性アルゴリズム多項式計算時間と非決定性アルゴリズム多項式計算時間を表すのだけどまぁ特別解説できるほどの能力は持ち合わせていないので省略。
それにこれくらいの事はどうやら情報系は知っているらしいので今更いいか。

問題の意味がわかって初めて、この問題は本当にクレイジーなのだなと。数学科の人間にはお前はまだこの問題がどれ程難解なのか分かりきってない死ねと言われるだろうがあくまで感覚なので許して下さい。

まあ無事この本も読めたし、また集中してアルゴリズムの勉強を再開できるなぁ。