ややプログラム紀行

博士1年のプログラムに関する日記

演習3

おひさしぶりです!(これ毎回言ってる

最近は「演習3」という3つの研究室を周りながら論文を読んだり実装したりするっていう授業でずっと苦しんでたんですが、ようやく1つ目がおわりました😇

この演習3という授業、最初に研究室を第5希望まで書いてそこから3つ選ばれるという形式なので、大抵の人は第4、第5希望の研究室も1つくらいは行くハメになるのがつらいところで、自分もファーストシーズンで第4希望の研究室に行ってきました、、、

 

その研究室では計算量理論やグラフなどいわゆる競技プログラミングっぽいものを扱っており、なかなかハードルが高そうという印象しかなくて何となく遠ざけてたんですね

正直今所属してる学科に入る前は計算量理論にも興味あったんですけど、授業が具体的な問題(頂点被覆問題がうんたら~みたいな)ばかりで「まだ計算量理論は全然発展してないんだなぁ~」って印象になっていたってのもあると思います

 

それでも結局その研究室では計算量理論について勉強しました、せっかくだし

やった内容は結構難しかったので簡単に説明しにくいですが、

最初の方は「Parameterized Problem」という、問題の計算量をパラメータの導入によってより細かく解析しよう!みたいなものについて

後半は充足可能性問題のパラメータ込みの計算量を考えたとき、それをどこまで小さくできるかみたいな内容をやりました(説明になってねぇ

 

充足可能性問題の云々は結構おもしろかったのでかる~く説明すると、

・SAT問題とはこれ↓

ja.wikipedia.org

・AND(SAT)問題とは入力として命題n個受け取ったとき、それらがすべて充足可能であるか判定する問題

・問題の帰着とはある問題Pの入力xを答えを変えないように他の問題P'の入力x'に変換すること、つまりPにxを渡して答えがtrueならP'にx'を渡しても答えがtrue、逆もしかりとなるようにxをx'に変換すること

・問題Pがself-compressibleとはPの入力xを多項式時間でPの入力x'に変換できる、つまり自分自身に多項式時間で帰着できること

・AND(SAT)問題のパラメータとして命題n個のうちの最大長kとしたとき、AND(SAT)はstrongly self-compressibleであるか?、つまりself-compressibleかつ帰着後の入力x'がkの多項式で抑えられるか?を知りたい

・実は上の疑問の答えは「AND(SAT)はおそらくstrongly self-compressibleでない」となることが証明できる(この証明がわりとへぇ~ってなった

 

証明のステップはかなり長いから全然説明できない(60ページあった)んだけど、中心のアイディアは、

・AND(SAT)の代わりにOR(SAT)という命題n個に対しどれかしらが充足可能かを判定する問題を考えてみる

・OR(SAT)がstrongly self-compressibleだとして、その帰着をRとおくと、充足不能な命題x1~xnと充足可能な命題yに対して、(x1,...,xn)は当然OR(SAT)に渡せばfalseとなる一方、(x1,...,y,...,xn)みたいにxjをyに置き換えたものを考えてみるとこれはOR(SAT)でtrueになる

つまりR(x1,...,xn)とR(x1,...,y,...,xn)は全然違う値になっているはず!!という性質を利用して、OR(SAT)が統計的ゼロ知識証明というもので解けちゃうということが証明できちゃいます、ゼロ知識証明はこれ、名前がかっこいい

ja.wikipedia.org

 

 

雑に書いたからところどころ間違ってるとおもう^_^;、とくにcompressibleのあたり

これで興味沸いた人なんていないと思いますが、「New Limits to Classical and Quantum Instance Compression」って論文っす

 

こうして書いてみると学科に入ってから結構専門的なことやるようになったんだなーなんて気もする(説明が下手なだけ

文章を誰に向けて書いてるのかとくに考えてないせいでめちゃくちゃ中途半端な感じになってるけど気にしないでください

 

まぁとにかく一番心配してた研究室が終わってほっとしてます

 

この研究室で学べたことと言えば、研究は理想ばかり追ってるだけじゃだめなんだな~ってことですかね

理想を追うことはもちろん大事だしそれが動機になるんだとは思いますが、研究の世界はなかなか厳しいらしく常に成果をださなきゃいけないってことも考えると実現不可能な理想じゃなくて、理想を実現するために今できることを考えなきゃいけないんだなみたいな

 

次は機械学習の研究室で、自分自身わりとそこに興味あるんですがなにしろ知識がなさすぎてやばい

そろそろ院にむけて自分で論文あさったりし始めたほうがいいのかなぁ