理論計算機科学特論

岡本 吉央

テーマ：計算複雑性の基礎

注意：テーマは毎年変わる可能性があります

ショートカット： 講義資料 | コメント | レポート課題 | 公式シラバス | スケジュール | 参考文献 | 関連リンク | 過去の講義

実施形態

学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いません．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

講義資料

• 講義動画の再生リスト
• 4/28 (4) 領域計算量：L，NL，PSPACE
  • スライド
  • 講義動画
• 4/21 (3) 帰着と完全性：NP完全
  • スライド (4/22更新)
  • 講義動画
• 4/14 (2) 時間計算量：P, NP, coNP
  • スライド (4/15更新)
  • 講義動画
• 4/7 (1) 計算理論の復習
  • スライド (4/8更新)
  • 講義動画

• 4/28 (4) 領域計算量：L，NL，PSPACE
  • レポートを6回までか7回までか悩んでいるとのことでしたが、他の授業では7回までが多いので、他の授業と被らないために6回までだと少し余裕を持てます(要望ではなく、個人的な事情を述べただけ)。
    --ご提案ありがとうございます．ではそのようにします．
  • 説明が丁寧で授業のスピード感もちょうどよいと感じています。クイズの選択肢が面白くて楽しみにしています。
    --今日は時間が余ってしまったので，もう少しゆっくりでもよかったようです．時間の調整は難しいです．
  • 4の選択肢が、何かを参考にして書かれているのかどうか気になってしまいました
    --Geminiにいくつか候補を作ってもらって，その中で自分が気に入ったものを少しアレンジしています．
  • 呪術廻戦いいですよね
    --見たいと思っているのですが，時間がとれず，まだ1話も見れていません．(-_-;
  • 毎週クイズの4番楽しみにしています
    エヴァ世代かと思ったら呪術でびっくりしました
    --同じ時代を生きているのですから，世代は関係ないのです ;-)
  • 五条悟が好きなので､間違いとわかっていても4を選びたい自分がいます。
    --選んでいただいてもかまわないですよ．;-) (なお，今回は実際に4を選んだ人が割といました．)
  • GWの予定は決まってますか？
    --私はとくに決まった用事がないですが，府中市ではくらやみ祭が行われるので，それは楽しみにしています．
  • 先生はGWのご予定はありますか？私はデジタルデバイスを家において、本だけ持ってどこかぶらぶらする日を作ろうかなと考えています。
    --いわゆるデジタルデトックスですね．
  • 個人的には4年前のことはほぼ覚えてないので、大昔です
    --それは困りましたね :-)
  • ちょっと用事があって学校行くのが面倒(時間的には可能)だったので、Zoomあってありがたいなと思いました。
    --はい，ぜひ活かしてください．
  • 課題をやるのを忘れていてとても焦りました．なんとか間に合ってよかったです．
    --はい，忘れずに提出してください．
  • なし
    --これだと内容がないので，0.5点もありません．ご了承ください．
  • 時間計算量は理解していたが，空間計算量はうろ覚えだったのでこの授業で復習できたので嬉しい．
    --それはよかったです．後の講義では，いままで扱ってこなかった新しい内容も登場すると思いますので，お楽しみに．
  • NPの話は覚えていましたが、領域計算量の話はあまり覚えていなかったので復習したいと思います。
    --はい，ぜひ復習をしてください．
  • 時間計算量から空間計算量へとどんどん大きな話になっていて、面白い。
    --どんどん大きな話になっていますね．いろいろなものが計算理論の対象になることを感じてください．
  • 具体的な問題がないとどのクラスがどういう感じなのかが分かりにくいと思った
    --そうですね．NLやLの問題の例を挙げようと思っていたのですが，時間が足りなそうだと判断したので，後の方の授業に回すようにしました．ただ，せっかくコメントをいただいたので，ここで紹介します．(後の授業でも紹介します．)
    NLの問題の典型例はSTCONと呼ばれる次の問題です．入力として与えられるのは有向グラフG=(V,A)とその2頂点s,tです．出力は，sからtへ至る経路があればYes，そうでなければNoです．これが非決定性を持つ対数領域アルゴリズムで解けるのは次のように分かります．アルゴリズムではsからtまで歩いていく様子をイメージして，現在いる頂点の名を作業領域に保持します．(これは対数領域でできます．) 現在いる頂点から次の頂点をguessします．そして，そこへ移動します．これを繰り返すことでtにたどりつければYesを出力します．移動を頂点数の回数だけ繰り返してもtにたどり着けなければNoを出力します．
    Lの問題の典型例はUSTCONと呼ばれるもので，これはSTCONにおける「有向グラフ」を「無向グラフ」に変えたものです．これが非決定性を持たない対数領域アルゴリズムで解けることはかなり非自明で，2004年にはじめてそのようなアルゴリズムが作られました．
  • チューリングマシンには馴染みがあったが、あくまで計算モデルの一つとしての認識が強く、領域計算量やメモリの領域の話に目を向ける機会が少なかったため、いい勉強になった。
    --ひとつのものにもいろいろな側面がありますので，普段気にしていない側面を気にするというのは，そういうことに気づける機会になると思います．
  • 時間計算量だけでなく領域計算量も見ることが大切だとわかりました。
    --まずは大切だということを認識するのが大事ですね．授業がそのきっかけになれれば，私もうれしいです．
  • 領域計算量を気にしてプログラムを書いたことがありませんでした。授業中で紹介されていたアルゴリズム2は分かりやすく、領域計算量は自分がしたことのない考え方であったことに気づきました。
    --これを学んだときに私も感銘を受けました．好きな例です．
  • 本日の学習では，計算資源としての領域（空間）に着目し，その扱い方を理解することを目標とした。これまで計算量といえば時間に注目することが多かったが，実際にはメモリ使用量も重要な資源であり，問題の難しさを別の視点から捉えられる点が興味深かった。
    --そうですね．皆さんもプログラムを書いたりアルゴリズムを考えるときは，領域も気にするようにしてください．
  • 自分では領域計算量の削減アルゴリズムなんかはそう簡単に思いつける気はしないが、今回の例のように「こうすると領域計算量が削減できる」といった工夫は知るとすごい面白そうだな、と思った。
    --領域計算量の削減の例として，メモリやレジスタが限られる場合の話を授業ではしましたが，大規模なシステム (メモリや外部記憶が豊富にある場合) であっても，キャッシュ効率を考慮すると，領域計算量を削減して，参照局所性がうまく活かせるようにすることが重要になる場面も多くあります．
  • 資源・計算量・非決定性の3つの軸を使った計算量クラスの3次元的な図解が、直感的でおもしろかったです。
    --この図をいままで書いたことはなかったのですが，はじめて書いてみました．わかりやすくなったかどうかは私に自信がないのですが，なにかが伝わったのならよかったです．
  • 計算複雑性理論において時間と領域が全く互いに関係ない独立的な概念だと思ってましたが、今回の授業を通して密接な関係がと知りました。
    --この関係については次回また扱います．お楽しみに．
  • 計算資源には「時間・領域・非決定性」の3つの次元があることを示し、それらの関係性について知ることができた。次回以降の関係性の証明で、理解を深めたい。
    --証明は次回以降にたくさん持ち越しているので，持ち越した分の理解ができるようにしていきます．
  • 領域計算複雑性クラスについて学ぶことができた。個人的には時間計算複雑性クラスと領域計算複雑性クラスの間に包含関係が証明できるのが不思議と思う。次回が楽しみです。
    --ぜひ楽しみにしていてください．
  • PがLを含むなど，時間と領域という別々の資源に関する計算複雑性クラスにおいて，包含関係が存在するということに驚きました．
    --次回の授業のあとにはそのような関係が自然だと思えるように努めます．
  • 対数領域帰着がまだ不安
    --イメージがわきにくいのかもしれません．いろいろな問題を定数個の変数で解けるかどうか考えてみると，なれてくるかもしれません．
  • 対数領域帰着であれば多項式時間帰着であるように、時間を領域で表すことができるということに驚いた。
    --そうですね．時間と領域にはいろいろな関係があります．次回のテーマの1つになります．
  • 対数領域帰着の推移性の証明は多項式時間帰着の推移性のより少しテクニカルなものであったのでしっかり復習します。
    --たしかにテクニカルですね．領域だけを考える場合には，時間を考える必要がないことが重要です．
  • 推移性の証明のところが面白いと感じました．なぁなぁですませてしまいそうな感じのとこにも，領域計算量を考える必要がある点に興味深さを感じました．
    --述べている性質自体はいかにも成り立ちそうなことなのですが，それを証明するときにはいろいろなことを考える必要があるので，その点を見逃してはならないですね．
  • クイズの1の「入力IのO（log|I|）ビットだけ読むことで問題を解く」アルゴリズムが存在する問題について、入力を冗長にすれば任意の問題がその問題だと言えると思いますが、まとも？な入力でそうなる問題のクラスは考えられているのでしょうか。
    --論点は2つあります．(1) 「入力を冗長にする」ということにも処理が必要であることが重要です．入力Iに対して，冗長にする処理を行って冗長な入力I'を作ったとします．I'の符号長がIの符号長の多項式では収まらないとすると，アルゴリズム全体は対数領域アルゴリズムにならなくなってしまいます．(2) もともとの入力が冗長である場合があります (おそらく，これがコメントの真意だと思っています)．そのような場合には入力IのO(log|I|)ビットだけを読んで正しく解くことができる可能性があります．この論点については，さらに2つの論点があります．(2-1) 実をいうと，これは次回扱う「水増し論法」の要点につながってきます．(2-2) この論点は圧縮につながります．つまり，入力が冗長であるとき，それを圧縮すれば，冗長でない表現が得られることになります．圧縮後の表現の符号長がO(log|I|)であれば，線形領域アルゴリズムの領域計算量がO(log|I|)となり，|I|に関しては対数領域アルゴリズムになります．ただ，圧縮自体も対数領域でできる必要があります．
    すみません，質問自体に答えていないので，質問に答えます．普通は，まともな入力しか考えないことになっていて，入力の(ほぼ)全体を読まないと正しいYes/Noが答えられないとしています．つまり，必ず入力のΩ(|I|)ビットは読まないと正しい出力をするアルゴリズムにはならないと考えています．その意味では，入力のO(log|I|)ビットだけを読んで問題を解くことはできないと考えています．
  • 「ある定数$k$が存在して，$|R(I_1)| = O(|I_1|^k)$」が成り立つのは全然自明じゃないなと思っていたのですが，基本操作の性質を用いて，時点状況を数え上げるだけで証明ができるのは「おぉー」と思いました．
    --そうですね．これは時間と領域の関係を探るときによく行う論法で，次回にも登場します．
  • PにもP困難やP完全があることに驚きました。クイズは毎回答えとは別に、選びたくなる選択肢があるので面白いと思いました。
    --はい，PにもP困難やP完全というものがあります．これによってPの中の問題どうしの難しさを比べられるようになります．
  • 論理回路評価問題がP完全なのは何となくわかるが、論理式評価問題がP完全出ないのは不思議に思った。
    --計算理論にはそのように不思議な現象がいくつもあります．現象があるということは，計算というものが科学の対象になるということです．なぜそのような現象が起こるのかということを解明するのが，科学としての計算理論の目標になります．
  • 研究で実際の回路構造について扱うのですが、その過程でのCVP-likeな論理回路検証は一瞬で計算が完了するのに対してSAT-likeな合成・配線ではかなりの時間がかかるので感覚に説明がついたと思います。
    --論理回路の合成や配線は計算理論的にもよく研究されています．また，論理回路という計算モデルにおいては「面積」も資源であると考えられています．興味があれば，ぜひ調べてみてください．
  • この講義はP vs NPに焦点を当てたものではないのは承知の上で，なぜか先週からP vs NPのどこが難しいのだろうということが，特にお風呂に入っている間や通学中に気になってしょうがなくなってしまったので，そういうときに思いつくくらいの疑問を調べて「これくらいのことは調べられているんだな」ってことを繰り返しています．以前は，あまり深く考えもせずに「NP完全と言われている問題には，SATのような特定の条件を満たす組合せの存在を考慮する問題も多いし，それに対して多項式時間で動くアルゴリズムなんて作れる気がしないからP$\neq$NPなんじゃね」と思っていたのですが，調べれば調べるほどP$\neq$NPを言おうとするには，色々な設定(決定問題，チューリングマシン，クラスP，クラスNPの定義など)が絶妙すぎて，P$=$NPではないかという意見もあり得る意見なんだなと思えてきました．
    --P vs NP問題を解決すること自体の難しさは，計算複雑性理論においてずーっと調べられているテーマです．この流れについて授業で展開することもできたかもしれませんが，あまりに専門的すぎると思い，やめました．この流れにおいては特に「回路計算量」(circuit complexity) と呼ばれる概念が重要な役割を果たしますし，いまでも重要な役割を果たしています．
  • 本日も講義ありがとうございました。次回の水増し論法によるexptime →nexptimeの証明少し楽しみにしています。雑談なのですが、先生はゴールデンウィークのご予定どのような感じなのでしょうか。
    --水増し論法はよく出てくるものなので，ぜひ身につけてください．キツネにつままれたような感覚になるかもしれませんが，お楽しみに．
• 4/21 (3) 帰着と完全性：NP完全
  • サは横画が一画目らしいです
    --ありがとうございます．くさかんむりと同じ書き順なのですね．
  • カタカナに書き順があることを初めて知った
    --あります．日本人はかなり書き順を気にするように思います．毛筆にせよペン字にせよ，きれいに書くということに対する興味が強いように思います．
  • 最近論理素子の新たなJIS記号が話題になっていました。新しい方は基本的に全部長方形がベースで、果たしてこれで本当に分かりやすくなったのだろうかと個人的には疑問です…
    --JIS記号が改められたことを知りませんでした．ありがとうございます．工業的には見間違いや誤解を少なくすることと国際的に通用することが重要だと思います．分かりやすさは慣れにもよるかと思いますが，いずれにせよ，いろいろな標準が混在することはあまりよくないような気がします．
  • 論理素子の形は覚えていなかったので覚えなくて良いと言われて安心した。
    --なにもかも「覚える必要はない」と思ってください，必要なときに調べて思い出せれば十分です．慣れてきて自然と覚えてしまうことがあれば，それでよいと思います．
  • 31ページの論理回路の一番下のはOR素子なのではないかと思いました。
    --ご指摘のとおりです．ありがとうございます．論理式の方をANDに修正しました．
  • 先生も論理回路記号を覚えていなかったり、サの書き順が曖昧だったりと、身近に感じることができました。本日もためになる授業をありがとうございました。
    --何を通して身近に感じることができるのかということも人それぞれだとわかりました．ありがとうございます．
  • 論理素子や論理回路は馴染みがあって内容が入ってきやすかったです
    --それはよかったです．論理回路は計算モデルのひとつなので，計算複雑性の理論においても重要な役割を果たします．しかし，この授業ではその深みにはあまり入っていかないことになります．
  • チューリングマシンを考えることで、計算機の原理（0, 1の信号処理）の理解を深められた。
    --ちょっとこれは今回の授業の内容とはあまり関係ないかもしれません．そうであっても，何かの理解が深まったのなら，よかったです．
  • ないです
    --これは内容がないです．(-_-;
  • 特にありません
    --こちらも内容がないという判断になります．雑談でもよいので，何か書いてください．
  • ご返答ありがとうございます。次回から、「13時までに提出」という文言だけで提出するのはやめようと思います。
    --はい，何か私へのフィードバックになることを，雑談でもよいので，提出してください．
  • 最近暑すぎます
    --私もそう思います．;-)
  • 最近気温の上がり下がりが激しいのでお互い体調に気をつけましょう
    --そうですね．お互いに気を付けましょう．
  • 本日もありがとうございました。だんだんと暑くなってきてもう半袖の季節ですね。
    --そうですね．ただ，まだ涼しい日もあるようなので，気を付けてください．
  • しばらくオンラインなので、生活リズムを整えるのにちょうどいいです。
    --はい，オンラインでも構わないので，ぜひご参加ください．
  • 最初に前回の復習があって助かりました。途中休憩が入る授業があまりないのでありがたいです。
    --休憩は私の勝手な都合でいれていますが，皆さんにも都合がよいのではないかと勝手に思っています．
  • ありがとうございました！
    --こちらこそありがとうございました．
  • 自分の研究内容とかなり被っていて毎回面白いです．
    --それはよかったです．ぜひご自身の研究に活かせるようにしてください．
  • ある仮定が成り立つ上でどうなるか考えている、というのにまだ慣れない。
    今回は一回聞いただけではわからなかったところが多かったのでよく復習したいと思う。
    --このような考え方は計算理論で良く行うわけですが，それに限らず，とても重要な考え方だと思います．そのような考え方ができないと，現世に存在するものから推論をすることしかできなくなり，不確実性に対応できません．ぜひ身につけてください．
  • CIRCUIT-SAT はNP困難であることの証明において、証拠を検証する多項式時間アルゴリズムを論理回路で実装するとのことであったが、実際にどのように実装するのか気になったので少し考えてみようと思いました。
    --この証明はわりと入り組んでいます (アイディアは授業で紹介したようにわかりやすいのですが)．まず，チューリング機械を定義する必要があります．この定義が案外ややこしいです (ふたたび，アイディアはわりと単純なのですが)．そして，チューリング機械の振舞を論理回路として実現するわけです．
  • CNF SATがそもそも何でNP完全であるかはすぐに自分で証明できなかったのでそこを復習したいと思いました。
    --NPに入っていることは授業の内容で証明しているつもりになっているので，まずは，その部分を理解してください．
  • スライドの困難性の定義の文章中でC困難がC-completeと書いてありましたが、C困難はC-hardですか？
    --ご指摘のとおりです．授業中にも訂正したとおり，その「C-complete」は「C-hard」が正しいです．資料も修正しました．
  • 帰着と完全性について、復習して理解を深めたい。
    --はい，だんだんと難しくなってきていると思います．ぜひ復習してください．
  • NP完全とNP困難の違いが今までよく理母できていなかったが、今日の授業を通して理解することができた
    --それはよかったです．定義としても本質としてもはっきりと異なる概念なので，区別して理解してください．
  • 今回の講義で、完全性と困難性の理解が深まりました。
    --はい，今後もでてきますので，復習しておいてください．
  • NPと付いているのにNP困難がNP以外の範囲も含むイメージなのが、少し難しいと思いました。
    --たしかにそうだと思います．NP困難というのは，「NPより難しいか，あるいは同等に難しい」ということなので，「NP」がついています．NPの部分を他の複雑性クラスに変えると，この「NP」の部分がそのクラスに変わるわけです．
  • NP完全の意味がわかってきたので、以前読んだ論文を改めて読んでみようと思います。
    --ぜひお願いします．授業で扱ったことが研究や生活に活かせるようになることが大事だと思うので，試してみてください．
  • 一つでもNP完全問題が多項式時間で解けるということが証明できたら、P=NPの未解決問題を解決できると知って驚きました。それでもまだ証明されてないということは、P=NPが成立しない可能性の方が高そうだとは思いました。
    --この可能性についてはいろいろな議論があります．Bill Gasarchという研究者が「The Third P=?NP Open Poll」というタイトルの記事を書いています (出版年は2019で，オフィシャルなものはこちら，著者のコピーはこちら)．これによると，「P＝NPかP＝NPか」などの問いに著名な研究者が答えて，比率でいうと，88パーセントがP≠NPだと思っていて，12パーセントがP=NPだと思っているとのことです．よく「P≠NPであると広く信じられている」と書かれたりするのですが，この比率を見ると，それほど広く信じられているわけでもないように思います．
  • 先生はP=NPだと思いますか？P≠NPだと思いますか？どっちであって欲しいですか？
    --直前のコメントへの回答のように，＝であるか≠であるかという予想はなかなか私にはできません．「どっちであって欲しい」という願望については考えたことがありませんでした．Lance FortnowのThe Golden Ticketという本 (和訳あり) には，P=NPが正しい世界では，素晴らしい未来が開かれる様子が描かれています (それが素晴らしすぎるので，P=NPだと信じるのも難しいことが書いてあります)．ただ，その記述はあまりP=NPであることと関係がないように私には見えました．興味があればぜひこの本をご覧ください．
  • Pは決定的多項式で、NPは非決定的多項式のことだと思いますが、なぜP＝NPだと、NPが多項式時間で解けると言うのか？どちらかというと、P＝NPより決定性の問題(P)は，非決定性の問題(NP)と同じであり、NPが決定的に解けることにならないですか？
    NPは非決定的であるが、Pと同じ多項式であるため、決定性の関係を見ているように感じます。
    --単に「多項式時間で解ける」というときには非決定性のないアルゴリズムを暗に仮定しています．普通のプログラムでは非決定性を扱えないからです．そのため，非決定性を持つアルゴリズムを使って多項式時間で解けるときには「非決定性を使って多項式時間で解ける」などと言って，区別しています．
    それを踏まえて，質問にこたえると，P=NPということが「NPが決定的に解ける」ということを意味するというのは正しい理解です．
  • 帰着の概念は少し難しく毎回どちらがどちらに帰着されるのか取り違えることがあるので、気をつけたい。
    --そのとおりだと思います．覚えようとすると混乱するので，その都度考えて，正しい結論を導けるようにしてください．
  • 帰着が初めて聞く話で面白かったです！
    --それはよかったです．:-) これからも初めて聞く話が多くでてくると思います．
  • 帰着を構成する際に、どのような視点で「うまい変換」を見つければよいのかがまだ曖昧である。特に、既知のNP完全問題から新しい問題への帰着を考える際の典型的な発想法やコツがあれば知りたい。
    --初回でも話をしたように，個々の問題の難しさを解明することはこの授業では行いません．代わりに (といって，本当に代わりになるか分かりませんが) 以前別の授業でそのような話を1学期間行っていますので，そちらを参考にしてください．
  • 学域のMI実験の授業でCNF-SAT問題を解いたことを思い出しました。SATソルバというものがありまして、数独などいろいろな問題をSATに帰着させて解きました。
    --今回扱った帰着はSATソルバーを使うための基礎であると考えてもらってよいです．PをP'に帰着することで，P'を解くアルゴリズムがあればPも解けることになるわけですから，P'がSATであれば，Pを解くためにSATソルバーが使えるということになるわけです．帰着は問題解決においてとても有効な技法なのです．
  • 全ての問題クラスに完全問題が存在するわけではないと知り、無意識のうちにどのクラスにも存在するものと思い込んでいたため、非常に驚きました。
    --はい，そうなのです．よく誤解されます．正確にいうと「存在することが知られていない」ということになると思いますが，そのようなクラスの例はあとの方で登場する予定です．
  • クラスC, C'がC⊂C'を満たしているとき、問題P ∈ C' \ CでC困難でない問題は存在するのでしょうか?
    --結論からいえば，存在します．あとの授業で扱うLadnerの定理に関係しています．そのときにまた話をします．
  • 今回のクイズ難しかった．自分が1を選んだ理由は，消去法である．2はEXPTIMEに属する問題はNP困難だが，NP完全でないので不適．3は3SATはNP完全だが，2SATはPに属していたはず．4は意味が分からなかった．次週以降は，あまり知らない範囲になるので，理解できるか不安である．
    --過去2回に比べて難しかったですね．なお，正解は3です．
  • エヴァお好きですか？
    --Geminiの提案をもとに作ったものなので，あまり分かっていません．;-)
  • 空間と時間の複雑性の関係が気になっていたので次回が楽しみです。単一の生命に進化した人類ならP≠NPも証明できそうです。
    --そうですね．そのときは「おめでとう」と声をかけあってください．
  • 領域資源にはどのような課題が存在するのか、時間資源との関係はどうなるのか、楽しみです。
    --はい，次回の内容になります．お楽しみに．
  • 計算時間を資源とする考え方は親しみがありますが、領域を資源とする考え方はあまり馴染みがないため、次回以降の内容は少々不安です。ついていけるように頑張ります。
    --たとえば，小さなCPUではレジスタの数が限られているので，それをうまくやりくりしていろいろな処理をする必要があるわけです．これは領域が資源になっている例です．問題を解くときにどの程度の領域が必要となるのかということを議論していきます．
• 4/14 (2) 時間計算量：P, NP, coNP
  • コメントをありがとうございました．
  • 桜がもう葉桜になってきてる
    --そうですね．今年は桜の開花が早かったので，散るのも早いですね．
  • 本日も授業ありがとうございました。岡本先生の授業を昨年も履修しました。今年も単位取得できるように努めます。
    --はい，よろしくお願いします．
  • 急なneko punchに笑いました癒されました。
    --癒されたのでしたらよかったです．:-)
  • 1限来るのが辛い。新宿駅での乗り換え人多すぎて遅れそうになる。
    --お察しします．ぜひ慣れてください．
  • 興味深い授業でした．
    --次回以降も興味深くありますように．
  • とてもわかりやすかったです！
    --わからないことがでてきたら，ぜひ質問してください．
  • わかりやすかったです！
    --わからないことがでてきたら，ぜひ質問してください．
  • わかりやすかったです。
    --わからないことがでてきたら，ぜひ質問してください．
  • とくにないです
    --すみませんが，このコメントでは内容がないので，0.5点はありません．
  • 特にありません
    --すみませんが，このコメントでは内容がないので，0.5点はありません．
  • 13時までに回答しました。という文だと0.5点はいただけますでしょうか。
    --「13時までに回答しました」というのは授業に対するコメントでも雑談でもないので，0.5点にはならないと思ってください．ただ「13時までに回答しました。という分だと0.5点はいただけますでしょうか。」は質問なので，0.5点になります．
  • 自分が作成しているプログラムでは時間計算量に着目したことがあまりなかったので，確認してみたいと思いました．
    --ぜひ確認してください．確認できるようになることができれば，それだけでこの授業を受けた価値があります．
  • 学部で習った時間計算量についての問題などが図解されており分かりやすかった
    --図は重要だと考えています．図で理解が進むと思っているので．
  • 階層がたくさん考えられそうだというのはなんとなくわかったが、無限にあるというイメージがまだできない。
    --これは今後の授業の話になります．いまのところ，PとEXPTIMEの間にはNPとcoNPがあるというところまで話が進んでいると思ってください．
  • 何回か聞いたことのあるPやNPの話を聞けてよかった
    --まずは，PとNPが何であるかという定義を理解できることが大事だと思います．ぜひ身につけてください．
  • P≠NP問題について、名前は知っていたがどんな問題なのかよくわからなかったので、今回知れてうれしい
    --はい，情報系の素養としては「知っていて当然」のような内容ではあるので，ぜひ身につけてください．
  • 非決定性アルゴリズムとはどういうものかを自分の中でまとめられていないので、録画を見て復習します。
    --非決定性を理解するのはなかなか難しいと思います．ぜひ復習してください．
  • PとNPしか知らなかったので、計算複雑性のクラスは自分が思っているよりも多く分類できるのだと思った。
    --この後の授業で他にもいろいろと登場する予定です．お楽しみに．
  • 授業中の包含関係の証明が鮮やかだっただけに、P＝NP問題等が未解決であるというギャップがとても興味深く感じました。今後講義を受けて理解を深めていくことが楽しみです。
    --片方の包含関係 (⊆) は割と簡単に証明できることが多いです．難しいのは等号 (＝) だったり，その否定 (≠) だったりします．
  • 順を追って一つ一つ丁寧に解説していただけたので，とてもわかりやすかったです．
    --順は追っていたのですが，あまりストーリーがなかったように自分でも思いました．おそらく「なぜ非決定性を考えるのか」とか「なぜ補問題を考えるのか」ということはあまり明確ではなかった気がします．反省しています．
  • 補クラスという概念を初めて習ったのでこれからもっと知見を深めていきたいです．
    --はい，補クラスは今後もでてきて，深めていきます．
  • 補問題と非決定性の部分について、1回聞いただけではあまり理解できなかった為、復習して理解を深めたい。
    --動画もありますので，ぜひ復習してください．
  • 補問題について素数判定の例がすごくわかりやすかった．次回の帰着の定義について厳密に理解しようと思う．
    --素数判定はcoNPの問題としてはよく出てくる例だと思います．次回は別の例を見ます．
  • 計算複雑性の分野ではクラス間の関係について未解決問題がたくさんあって驚いた。
    --はい，ほとんどすべてのことが未解決です．そのため，解決している一部のことはとても貴重です．その一部は後の授業で紹介します．
  • クラス間の関係の証明の部分は少し理解が難しく感じました
    --難しいですよね．証明をちゃんと書き下していないのがよくないかもしれません．
  • 図や例があるおかげで、補問題あたりの話はなんとか理解できた気になれた。
    --理解した気になってもらうのが私の目標なので，それは達成できていそうですね．
  • 時間は資源という考えで進めるのが興味深かったです。np完全について調べてみようと思います。
    --NP完全性は次回の内容になります．ぜひ予習してください．
  • 研究分野と近い話だったので楽しめました。
    --それはよかったです，ぜひ研究に役立ててください．
  • P VS NP問題は学域での講義や、ゼミでの輪講にて学んでいたが、改めて復習できてよかった。指数時間アルゴリズムのクラスをEXPTIMEと表記するのは知らなかった。次回以降、オラクルが出てくる気がする。
    --EXPTIMEの定義は割と混乱しがちなものなので，気をつけてください．なお，オラクルはでてこない予定です (予定はかわるかもしれませんが)．
  • P≠EXPTIMEの証明がどのようなものになるのか気になった。それぞれのクラス間の関係で未解決問題が多くあることに驚いた。
    --P≠EXPTIMEは第6回の授業で扱う予定です．
  • PとNPは聞いたことがありましたが定義は覚えていなかったので、定義が違うのにイコールでないかもイコールかもわからないのが面白いと思いました。また、coNPは知らなかったので、任意と存在が反対になってしまうせいでNPと同じクラスとできないのが面白いと思いました。
    --「任意」と「存在」をうまく扱うことが非決定性や指数時間をうまく扱う際のポイントとなってくる，というのが今後の内容につながってきます．今後も気にしていてください．
  • 計算複雑性クラスとその包含関係についてまだ初歩的ではあると思うが学べてよかった。特に、NPはNon Polynomialの略だと勝手に思っていたので、Non-deterministic Polynomialであると学べて良かった。
    --NPをNon Polynomialだと思ってしまうという誤解はよくあるものなので，その誤解がとけたならばうれしいです．
  • 今回のクイズでもでましたが、NPがただ単に「多項式でない」と今日の授業までに思っていました。「非決定性」と言う、さら難しい概念に関係していることを知りました。
    --非決定性は計算において重要な概念です．授業でも述べましたが，非決定性をそのまま普通のプログラムで表すことはできないのですが，非決定性を通していろいろなものを考えることで，見通しがよくなったりします．ぜひ身につけてください．
  • 定義だけを聞いてると、P≠NPであるように感じられます。多項式時間でも、非決定性アルゴリズムは指数個の要素からguessで好きな要素を選べる点が、とても強力だと思うからです。しかし、有限オートマトンのように決定性と非決定性に差がないクラスもあって、難しいですね...
    --決定性と非決定性の差があるかないかというのはなかなか難しい問題です．後の方の授業で扱いますが，領域という資源においては，決定性と非決定性に差がない場合があります．非決定性のほんとうの威力を私たちはまだ理解できていないのだと思います．
  • guessで好きなように選べるなら、非決定性アルゴリズムで入力がYesインスタンスのときは、最も早くYesとなる経路を選びたい
    --たしかにそうですね．このように非決定性を思い通りに扱うことができるとよいのですが，これはこれで計算複雑性の別の課題に踏み込んでいくことになります．特にランダム性と関係していることが知られていて，もしかしたら，後の方の授業で少し紹介することができるかもしれません．
• 4/7 (1) 計算理論の復習
  • コメントをありがとうございました．以下のように掲載されます．
  • 非常にわかりやすくご教示いただき誠にありがとうございました。次回以降が本番かと思いますが、今後解釈がずれていると非常に困りそうな前提知識を明瞭に整理していただき大変助かりました。本日は都合によりオンラインで受講いたしましたが、Zoom経由ですと時々声が遠くなるタイミングがあったので、可能であればマイク等調整していただけますと大変ありがたいです。次回以降は極力対面で直接受講するように努めます。
    --音声の件はすみません．動画の方も音声がうまく拾えていない部分があり，とても聞きにくくなっています．次回は改善を試みます．
  • 少し早口なため聞き取り辛い。
    講義スライドは理解しやすい内容で安心している。
    大学院の講義についていけるかとても不安。
    --はい，早口すぎて自分でも驚きました．時間どおりに終わるはずだったのに20分ぐらい余ってしまいました．次回以降気をつけます．
  • よろしくお願いします。
    --はい，よろしくお願いします．
  • 受講します。よろしくお願いします。
    --はい，こちらこそよろしくお願いします．
  • まだ確定してませんが、この授業を履修すると岡本先生の授業を取るのが3回目になります。その場合はよろしくお願いします。
    --ほぼ，熱狂的なファンですね ;-)
  • 授業ありがとうございました。半年間よろしくお願いします。
    --はい，よろしくお願いします．
  • ちょうど自分の知りたい分野を学べそうな講義だった。次回以降も受けたい。
    --はい，よろしくお願いします．
  • まだ履修するかはわかりませんが、頑張ります
    --履修する場合，履修登録期間中に忘れずに登録するようにしてください．
  • まだ履修するかは未定ですが、頑張ります
    --履修登録期間中に忘れずに登録するようにしてください．
  • 履修する聴講するか迷っています。興味のある分野なので次回も受講してみます。
    --履修登録期間中に忘れずに登録するようにしてください．
  • 内容が難しそうですが頑張ってついていきます。よろしくお願いします。
    --大学院の授業ですから，ある程度は難しいという覚悟は必要です．よろしくお願いします．
  • 計算複雑性についてはほとんど考えてこなかったが、プログラミングなどで考えると必要なのかもしれないと思った。
    --計算理論を勉強すると，日々の具体的なプログラミングを超えて，もっと抽象的に計算を考えることができるようになります．その味わいを楽しんでください．
  • 自分の研究と関わりのある分野なので次回以降も楽しみにしています．
    --計算複雑性はいろいろな分野と係わりがあるので，いろんな場面でその考え方は役立つと思います．
  • 先月の研究集会の時に計算量について質問頂きましたが、自分自身よくわからない部分が多いので、この授業を通して、少しでも理解できるようにしたいと思いました。
    --はい，ぜひ理解できるようにしていってください．
  • 自分は計算理論について研究しているので、今後の講義が楽しみです。
    --その場合は研究に直結しそうですね．楽しみにしてください．
  • 計算モデルについて学習できて面白いと思いました。前期よろしくお願いします
    --計算モデル自体の話は奥深いのですが，この授業ではあまり扱いませんし，まじめに扱いません．その点はご了承ください．
  • 面白いと思いましたが、用語などの理解ができるか自信がないので、復習しようと改めて思いました。
    --慣れない用語の理解はときに難しいと感じると思いますが，学部レベルのアルゴリズムや離散数学の考え方に慣れていれば理解できるように話を進めていくつもりです．よろしくお願いします．
  • チューリング機械をそのまま扱わないと聞いて安心しました
    --チューリング機械は直感的であるものの，実際にチューリング機械で動くアルゴリズムを書こうとすると，かなりややこしいです．そのため，この授業ではそれを避けて，直感的に理解できることを優先します．実際，論文などではそのような直感的な書き方がされることも多く，計算理論において広く受け入れられた取り扱い方だと思います．
  • アルゴリズムの概念は勉強になると感じた。
    --はい，勉強になると思います．ぜひ勉強してください．
  • 万能性について、万能性を持つ計算機を問題として解釈すると、それにシミュレートされるプログラム、計算機はインスタンスと考えることができるのだろうか。
    --はい，インスタンスと考えることができます．「インスタンス」は「入力」の言い換えだと思ってもらって大丈夫です．
  • アルゴリズムが別のアルゴリズムの入力になるということを考えたことがありませんでした。pc上で何かのファイルを実行するならその実行ファイルが入力になるという認識であっていますか。
    --その認識でだいたい合っています．万能性が重要なのは，それを同じ計算モデル (プログラミング言語) で行えるというところです．PythonのインタプリタをPythonで書くようなことをイメージしてください．
  • 有向グラフや無向グラフの定義を改めて復習することができた。万能性という性質について初めて知り興味深かった。
    --万能性は計算におけるとても重要な性質です．まずは，そういうものがあるということを気に留めてください．
  • 自分は計算複雑性についての研究をしているので、今後の講義が楽しみです。
    計算複雑性について今まで研究のためある程度は勉強してきましたが、NL=coNL辺りからは知らない話が多そうなので、理解できるようにしたいと思います。
    --NL=coNLは今となっては授業で扱える程度にまで整理されましたが，発見されたときには大きな驚きをもって迎えられたそうです．お楽しみに．
  • ビッグOの表記について復習する必要があると感じたので、次回までに済ませておきます。次回以降に扱う問題クラスについて説明があると嬉しいです。これから半年間よろしくお願いします。
    --扱うクラスの一部（ほぼすべて）はシラバスの各回に書いています．説明をするのは難しいので，もし興味があれば，シラバスを見て予習してください．
  • テーマが非常に面白そうでとてもワクワクしています。
    --私もワクワクしています．:-)
  • 計算複雑性クラスがP、NP、NP完全、NP困難だけだと思っていましたが、こんなに大量に色々あると今日まで考えたことすらありませんでした。この授業を通してできるだけ多くの計算複雑性クラスを一つ一つ理解していきたいです。
    --PやNPが有名なものであるのは疑いようがないのですが，他のクラスも普通に登場します．特に，プログラミング言語とかデータベース，人工知能においてはNPよりも上のクラス (NPを含むクラス) が重要になってきます．また，後のほうで扱うインタラクションのある計算モデルは暗号や通信でも重要な役割を果たします．
  • 抽象的な概念が多くて数学の講義を受けてるみたいだった．
    --計算理論はかなり抽象的で，そのため，数学的な考え方をよくします．授業でも述べましたが，証明も行っていきます．
  • 論文を読むにあたり計算複雑性について学ぶ必要があると感じたので、特にNP完全の知識を得られるように学習しようと思います。
    --NP完全性は第3回で扱う予定です．
  • 岡本先生の授業を履修するのは初めてで、よく離散最適化系のYouTubeとかは拝見させていただいてました。どの授業も資料のクオリティが高くわかりやすいのでわからないことがあった時とかはよく参考にさせていただいています。最近は楕円体法の理解の際におせわになりました。
    これから少しの間ですがよろしくお願いいたします。
    --理解のお役に立てたのならば，なによりです．
  • 23・8=184ビットではないのですか？　
    --はい，ご指摘のとおりです．スライドは修正しました．
  • 符号長のスライドで23×8は184だと思います、！
    --「分数ができない大学生」という本がありますが，皆さんが見ているのは「かけ算ができない大学教授」です．
  • スライド29の文字2の符号が間違っていると思います。
    --たしかに！ ご指摘ありがとうございます．スライドは修正しました．
  • 昨日の入学式で学部の1年生と話しましたが，若すぎて自身の老いを実感しました！
    --新入生のふりをして正門から入構してみて，勧誘のビラをもらえたら，若さを実感できると思います．
  • 13時までにクラスルームで回答
    --このコメントだと0.5点は与えられないことになります．ご注意ください．
  • complexity zoo のような曼荼羅を見るとワクワクします
    --Complexity Zooにあるものをすべて扱うわけではありませんので，それはご了承ください．;-)
  • もともと知っていた計算複雑性クラスが授業スライドのP7で挙げられていたものぐらいだったので、Complexity Zooを見てこんなに分類されてるんだと驚きました。
    --そうですね．それぞれのクラスは計算について何かしらの必要性があって導入されています，この授業ではその必要性まで迫れないかもしれませんが，その雰囲気はお伝えできればと思います．
  • 再帰やオーダー計算の復習をして、授業に臨もうと思いました。授業内容を覚えるのではなく、理解することに努めようと思います。
    --覚えようとするのは時間の無駄なので，覚えることを目的にはしないようにしてください．
  • さまざまな対象が最終的に0と1の列で表せるという点に、計算の本質的な統一性を感じた。
    一方で、表現の仕方によって扱いやすさが変わる点に、難しさと奥深さを感じた。
    --「さまざまな対象が最終的に0と1の列で表せる」というのは，情報を取り扱うときの視点として重要なことです．ぜひ身につけてください．
  • 中学高校の数学では，「解け」という言葉を定義もせずに簡単に使いすぎだという話が納得感があり面白かったです
    --本当にそう思っています．「解く」という言葉だけでなく，いろいろな言葉があいまいに使われていると思っています．みなさんもぜひ気にするようにしてください．

• 評価は毎回のクイズ，コメント投稿と2回のレポート課題により行う予定でいます．
• 毎回のクイズ，コメント投稿はGoogle Classroomのフォームで行います．

• こちらをご覧ください

• 4/7 (1) 計算理論の復習
• 4/14 (2) 時間計算量：P, NP, coNP
• 4/21 (3) 帰着と完全性：NP完全
• 4/28 (4) 領域計算量：L，NL，PSPACE
• 5/5 休み（祝日）
• 5/12 (5) 時間と領域の関係：P⊆PSPACE⊆EXPTIME
• 5/19 (6) 階層定理：P≠EXPTIME
• 5/26 (7) Ladnerの定理：P≠NP => NP-P≠NPC
• 6/2 (8) Savitchの定理：PSPACE=NPSPACE
• 6/9 (9) Immerman-Szelepcsényiの定理：NL = coNL
• 6/16 (10) 多項式階層：P=NP => P=PH
• 6/23 (11) 交代性計算：AP=PSPACE
• 6/30 (12) 確率的計算：BPP⊆PP, NP⊆PP
• 7/7 (13) 対話証明系 (1)：MA，AM，NP⊆MA⊆AM
• 7/14 (14) 対話証明系 (2)：IP⊆PSPACE
• 7/21 (15) 対話証明系 (3)：PSPACE⊆IP (オンデマンドの予定)
• 7/28 休み（授業のない日）

• Michael Sipser, Introduction to the Theory of Computation.
• Sanjeev Arora and Boaz Barak, Computational Complexity Theory: A Modern Approach.

• Complexity Zoo