理論計算機科学特論

岡本 吉央

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

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

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

実施形態

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

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

講義資料

• 講義動画の再生リスト
• 5/26 (7) Ladnerの定理：P≠NP => NP-P≠NPC
  • スライド (5/26更新)
  • 講義動画
• 5/19 (6) 階層定理：P≠EXPTIME
  • スライド (5/20更新)
  • 講義動画
• 5/12 (5) 時間と領域の関係：P⊆PSPACE⊆EXPTIME
  • スライド (5/12更新)
  • 講義動画
• 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更新)
  • 講義動画

• 5/26 (7) Ladnerの定理：P≠NP => NP-P≠NPC
  • 今，調布のバサラで牡蠣がめっちゃ安く食べれますよ！
    --あからさまな宣伝ですね :-) ちょっと今週は時間がないかもしれません．せっかくおすすめしていただいたのに，すみません．
  • 朝ごはん食べてないので、チョココロネを見てお腹が空きました。
    --朝食はとるほうがよいそうです．ぜひ食べてください．
  • 私はチョココロネを後ろから食べる派です。
    --どちらが後ろなのか，よくわかりません -_-;
  • 僕は頭から食べる派です
    --どちらが頭なのか，よくわかりません -_-; 広い方が頭でしょうか？
  • 私はチョココロネはしっぽから食べます！
    --「しっぽ」といわれれば細い方のように思えます．ふしぎですね．
  • 僕は､チョココロネが好きです。どちらから食べるのかはとても重要なことだと思われますこれについては深く議論するべきです。
    --私は両側から交互に食べているような気がします．クリームが出てきそうになったら，そちらをケアしていくのです．変でしょうか．
  • いつもとは違いチョココロネでびっくりしました。最近暑くなってきたので体調に気をつけてください！
    --実はアニメネタです．
  • 「チョココロネをどちらから食べるか」という問題から，私はあるアニメを連想するのですが，なんと来年で放映から20年が経つらしいです．？？？「ヨーグルトを，かき混ぜて，パン工場～♪」
    --すみません，古すぎたかもしれません．Geminiが作ったものを載せてるだけなので，あまり気にしていませんでした．
  • 小学生から好きな嵐が活動終了してしまうので、メンタルにきています
    --それは長い間好きだったのですね．このように活動終了をしっかりとした形で行うグループはあまりないような気がするので，その点は素晴らしい気がします．
  • 今週末の日曜日に嵐が活動終了するのが悲しい。我が家は配信チケットを購入し、家で視聴するつもりです。
    --現地に行くのはかなり難しいですからね．
  • 今朝は，バスの遅延 (地元のバスは晴れていればめったに遅延しないのですが，なぜか今朝は降車する駅に到着する時刻が遅かったです) と，京王線の人身事故 (府中-飛田給間で人身事故があったそうです) が重なって，講義開始に到着が間に合いませんでした．
    --それはお気の毒でした．
  • 効率的に頭を回復させる方法を存じ上げませんか？やるべきことが増えて、十分に休む時間がないため困っています。
    --私も知りたいです．私は疲れると活動がストップして，強制的に休む時間にはいってしまいます．それも困りごとです．
  • この授業のおかげで火曜日も早起きできていい朝を送れてます。
    --それはよいですね :-)
  • すべての多項式時間アルゴリズムの列挙のあたりから理解が難しかったので復習しようと思います。
    --そうですね．ぜひ復習をしてください．
  • 非可算集合に対しても，集合の元の列挙というのは考えられるのでしょうか．$h$を作るときの列挙について，問題もアルゴリズムもアルファベット (有限集合，ただし要素数は$2$以上とする) を定めて符号化したとしても，文字列 (自然数を文字に対応させる写像) 全体は非可算になってしまうので (P問題全体や対応するアルゴリズム全体は，文字列全体の部分集合なので実は可算なのかもしれませんが) 気になりました．
    --非可算集合に対してそのような列挙は考えられないものだという捉え方をしています．列挙は「自然数の集合との1対1対応をつくること」と見なすことが普通で，それは可算集合に対してしか行うことができないからです．
    一方で，有限文字列の集合は (アルファベットが有限集合ならば) 可算です．長さnの文字列の集合は高々有限なので，たとえば，まずは長さで並べて，同じ長さならば辞書順で並べるようにすれば，自然数全体の集合と1対1対応を作れます．(すみません，少し間違っていた部分を掲載後に修正しました．)
  • 水増し SAT は人工的な問題として作られていますが，「人工的でない NP 中間問題」が存在するなら，計算複雑性の構造をかなり深く理解できそうだと思いました。
    --そうですね．グラフ同型性問題は人工的でないNP中間問題の候補の1つですが，他にも候補は知られています．例えば，wikipediaの記事を見ると，いくつか挙げられています．参考にしてください．
  • グラフ同型性問題は感覚ではわかるが証明するのは難しそう。
    --わりととっつきにくい問題であると思われています．よく「グラフ同型性問題を多項式時間で解いた」と主張する論文がでてきますが，たいてい間違っていますし，間違い方もたいてい同じです．それはWeisfeiler-Lemanアルゴリズムという有名なアルゴリズムを再発明して，それが多項式時間アルゴリズムであると主張するものです．しかし，残念ながら，このアルゴリズムが多項式時間アルゴリズムではないこと (多項式時間で収まらないような入力が存在すること) はよく知られています (Cai, Fürer, Immerman '92)．古きをたずねることは大事だと教えられている気がします．
  • 無向グラフ同型判定問題で群論が活躍しているという話を聞いて興味深いと思いました。群論って本当に色んなところで出てきますね。
    --群は基本的な道具です．そのためにいろいろなところに出てきます．グラフの同型性においては，GからGへの同型写像全体というものが群を成します (Gの自己同型群と呼んだりします)．グラフの自己同型群が何になりうるのかということは，いわゆる「代数的グラフ理論 (Algebraic Graph Theory)」において重要な研究テーマになっています．
  • 普段からNP完全問題についてはよく研究で扱っているが、NP中間問題についてはほぼほぼ考えたことがなかったので、新たな知識を得られてとても勉強になった。
    --それはよかったです．授業を受けた甲斐がありますね．
  • Ladnerの定理は証明を理解するのが難しかったが、「P \neq NP ならば NP中間問題が存在する」ということが成り立つのはとりあえず理解できました。
    --証明に対する理解は「こういうのもあるのだな」という程度で十分です．まずはこのような事実が知られていることをお伝えしたかったので，それが理解できれば十分です．
  • 今回のLadnerの定理の証明は追うのが難しく感じましたが，この科目の中で最も理解しにくい証明だとおっしゃっていたので，授業後も頑張って資料を見ながら理解できるように努めたいと思います。
    --今回の証明は私もあまりその本質を分かっていない気がします．もう少し見通しのよい証明ができないものかと思ったりします．
  • h(n)の構成がまだ腑に落ちてないので、もう一度復習します。
    --はい，ここが難しい部分で，私もまだ腑に落ちていません．理解できたらぜひ教えてください．
  • しっかりと復習しておきたい
    --はい，しっかりと復習をお願いします．
  • Ladner の定理の逆はどうして成り立たないですか？
    --何を逆だと思うのかということによりますが，「NP完全ではない問題がNP-Pに存在する ⇒ P≠NP」を逆だとするならば，これは成り立ちます．なぜかといえば，NP-Pに属する問題があれば，それがP≠NPの証拠になるからです．そのような問題がNP完全でない必要もありません．
  • ビッグオー記法の定義に戻れば，何も間違っていないことは分かるのですが，スライド14/38ページにあるように「$\text{時間計算量 } = O(n + n^{h(n} + n^k) = O((n + n^{h(n))^k)$」と書かれると「非対称な関係なのに，どうして等号を使うことが伝統になってしまったのだろう…」と思ってしまいます．
    --はい，これはオーダー記法において「＝」という記号が特殊な使い方をされていることに起因します．たしかに分かりにくいです．オーダー記法においては，左辺に属する関数が右辺にも属するということを「＝」が意味します．
  • スライド23/38は関数$h$が$h \colon \mathbb{N} \to \mathbb{N}$であることがミソですね．鳩ノ巣原理だと思ったのですが，この認識は合ってますか．
    --鳩ノ巣原理であるという認識で正しいです．
  • 計算複雑性理論が、単に「解ける・解けない」の二元論ではなく、条件付き（P ≠ NP）の下で初めて複雑性の階層構造を導けると再認識できた
    --そうですね．そのような考え方を計算理論においてよく行います．これはおそらく計算理論だけでなくても，皆さんの生活や研究においても「○○ができると仮定すれば，△△ができる」という考え方を行うことが重要だということにつながっていくと思います．
  • 私の分野だとそこまで見ないのですが(リサーチ不足かもしれない)、一つの命題に対して複数の証明を行うことは計算複雑性の分野だとよくあるんでしょうか？
    --計算複雑性の分野でなくても，数学的な分野においてはよくあると思います．特に，重要な定理に対しては，複数の証明を行うことで，その定理の本質が見えてくることがあります．証明できたという事実だけが重要なのではなく，その証明自体の考え方も重要であると見ているのだと思います．
  • 今までの講義で一番わくわくした内容だった．第十回の授業のSigma_2^p，Pi_2^pに関する内容をとても知りたくなりました．
    --それはよかったです．第10回は多項式階層というものを扱います．お楽しみに．
  • P=NPなのかどうかが生きてるうちに証明されて欲しい
    --私も知りたいです :-)
  • これまでNP完全の定義が少し曖昧だったのですが，今回の授業を通して理解を深めることができました．
    --それはよかったです．ぜひ復習もしてください．
  • 授業の半分が終わってしまったのでレポート課題の勉強もかねて前半の内容の復習をしてみようと思います
    --はい，復習をおこなうよいタイミングなのかもしれませんね．
  • Savitchの定理はちょうど明日のゼミで扱うので良い復習になりそう
    --そうなのですね．おそらく授業では教科書に書いてある証明とすこし違う紹介の仕方をすることになると思います (本質は変わりませんが)．お楽しみに．
  • レポート課題が出されていましたが，今までの授業内容で理解しきれていない部分があるので，復習もかねて，取り組んでみようと思います．
    --はい，ぜひ取り組んでください．
  • 他の授業のレポート課題よりも先に提示していただいたので早めに取り組みたいと思います。
    --忘れずに提出するようにしてください．
  • レポートの問2の解答を作成するのが楽しみです
    --これを楽しみに思ってもらえてよかったです．生成AIの時代を考慮して，わりと「ふわふわ」な課題を出すことにしてみました．生成AIの力を借りながら考えてみてください．
  • レポート問題の駆け引き面白いです。意外と簡単そうなトピックを皆避けてそこが最高点が高くなるということもありえそうですね。
    --あんまりギャンブル的にするつもりはなかったのですが，結果的にそうなってしまうかもしれません．:-) 一応「考察が難しいトピックは選ばれにくい」と見なしているので，そのような点数にしようと考えてみました．
  • レポート頑張ります！
    --はい，しっかりと取り組んでください．
• 5/19 (6) 階層定理：P≠EXPTIME
  • [重要] スライド31、32ページのO(|s|)はO(f(|s|))ではないでしょうか？
    --はい，そのとおりです．すみません．そのあとで $\sqrt{n}$ が時間構成可能ではないことを説明しているときに，伝わっていない雰囲気を感じていたのですが，そこが間違っていることに私がきづいていませんでした ($O(f(|s|))$ になっていると思って説明していました．口頭では $O(|s|)$ だと言っているのに気づきませんでした．) スライドは修正しました．
  • 対角線論法のところで、Bが多項式時間である必要性がよく分からなかった。例えば、Pそのものについて考えてみても、P(P)がYesと仮定すると、Pの定義からP(P)はNoであり、矛盾が導かれる。そうすると、Pの定義そのものに矛盾があるのか……混乱してよく分からなくなってきました。自分の考えのどこに間違いがあるのかよく分からないままです…
    --$B(B)$ の出力がNoとなる理由として，ステップ数が $2^{|B|}$ を越える場合がないことをいうために，$B$ が多項式時間アルゴリズムであることを使っています．スライドの13/43ページです (PDFのページ番号では21です)．$B$ が多項式時間アルゴリズムなので，$B(B)$ の実行において費やすステップ数が $2^{|B|}$ を越えることがないのです．
  • P≠EXPTIMEの証明が，Bの矛盾で導かれるの興味深いと感じました
    --そうですね．味わい深いですね．
  • 今日の内容は普段よりも理解が難しかったので、復習が必要だと思いました。最後の出力を反転させるだけで、矛盾した状態になるのは面白いと思いました。
    --「反転させる」というのは対角線論法においてよく行います．ぜひ味わってください．
  • P \neq EXPTIME や PSPACE \neq EXPSPACE の証明は本当に騙されたような感じがして驚きました。
    --はい，私も騙されたような感じがしています．
  • PとPSPAPEの関係が知られていることは知らなかったので、とても面白かった。対角線論法は聞いたことがあったが、ここでも使われているのかと驚いた。
    --PとPSPACEの間の関係としてP⊆PSPACEが成り立つことは第5回の内容でした．ぜひ見直してください．
  • 計算量クラスの包含関係を図で整理して学んだことで，P，NP，PSPACE などの違いや未解決問題の位置づけが少し分かりやすくなった．特に「P ≠ EXPTIME」の証明に対角線論法を使う点が興味深かった．
    --そうですね．ただしく理解できていると思います．
  • 対角線論法を、時間階層定理の証明によって学ぶことができた。無条件下界を導けることがわかった。
    --そうですね．無条件下界を導けることはとても重要ですね．
  • 対角線論法の解説が気がつけば終わったように感じました。よくわからないので授業動画を見返します。
    --対角線論法は使っているだけですので，それ自体を深く理解しようということまでこの授業では行っていません．その点はご了承ください．
  • 対角線論法、実数全体集合と自然数全体集合の濃度が違うことを証明するときにも使いました。
    --対角線論法の典型例としては，その証明がよく登場します．実数全体の集合は自然数全体の集合より途轍もなく大きいのです．
  • チューリングマシンの停止性問題の証明でも、P≠EXPTIMEと同様に対角線論法が使われているので面白かったです．
    --そうですね．これも対角線論法の典型例だと思います．計算理論においてはいろいろな場面で対角線論法を使うことがあります．みなさんは計算理論の専門家ではないかもしれないので，今後あまり使うことはないかもしれませんが，もしどこかで出てきたら，いろいろなところで使えるのだな，と感じてください．
  • 計算複雑性の理論を勉強する際に時間階層定理は浅く知ってはいたが、実際に学ぶのは初めてだったのでとても興味深かった。
    --それはよかったです．何度も聞いているうちにだんだんと分かっていくこともあると思いますので，ぜひ活かしてください．
  • 対角線論法自体は知っていましたがこの領域で扱うことになるとは思っていなかったので面白かったです。
    --面白く感じてもらえて，うれしいです．
  • バベルの図書館の話があったので、前々から対角線論法には関心がありました。（さらに学域1年の離散数学でやったような気がしなくもないです）
    --「バベルの図書館」はむしろ巨大数の話と関係があるのかもしれません．巨大数も計算理論においては重要なトピックなのですが，私はあまり詳しくありません．(といっておきながら，『数学セミナー』では巨大数に関する記事を書いたことがあります．)
  • 時間階層定理は計算時間を増やすと解ける問題の範囲も広がるという計算理論の基本的で面白い考え方だと感じた。
    --時間階層定理では増やし方にはある程度の差がないといけないので，注意してください．例えば，多テープ・チューリング機械において，$\mathsf{TIME}(n)$ と $\mathsf{TIME}(n \log\log n)$ の間に差があるかどうかは時間階層定理から分からず，実際に差があるかどうかは未解決だと思います．
  • 時間階層定理の性質の部分はややこしいと思いました
    --そうですね．定義が間違っていた部分もあったので，スライドは修正しています．すみません．
  • この科目を履修する前は，P = NPでは，しらみ潰しで解ける問題が必ず多項式時間で解けるかどうかが問われていると誤解してましたが，実際にはEXPTIME困難問題で多項式時間で解けない問題が既にいくつも見つかっていることが知れてよかったです．
    --はい，この点はよく誤解されるので，今回の授業では強調したつもりですし，これが理解できたとしたら，この半年間の授業における目的に半分ぐらいは達成できています．
  • 今日の講義の最初の注意を聞くその時まで，PとNPを分離することを，多項式時間と指数時間を分離することだと勘違いしていた人です…．そうは言っても，非決定性を持つ計算モデルとして，例えば，モデルとして非決定性チューリングマシンを考えると，遷移関数の終域が (状態集合とアルファベットと{left,right}の直積) のべき集合になるので，この遷移関数を決定性チューリングマシン (遷移関数の終域が状態集合とアルファベットと{left,right}の直積であるもの) で，入力サイズの多項式ステップで模倣することを考えようとすると，指数関数と多項式関数の違いを見たくなるような気もするのです．…と，ここまで書いてみたのですが，書いたものだと，NPに属する問題が「非決定性チューリングマシンにおいて入力サイズの多項式ステップで解ける問題であること」は全く考えていないと思いました．ふむ…
    --例えば，有限状態オートマトンという計算モデルがありますが，それにおいては，非決定性があることとないことで，計算能力に差がないことが知られています．有限状態オートマトンによる計算というのは，「ワンパス」で計算する (入力を先頭から順に見ていき，戻って見直すことは行わない計算を行う) ことにだいたい対応するわけですが，それだけ計算手順に制限を設けると (つまり，計算資源を制限すると) 非決定性計算と決定性計算に差がないことになるわけです．非決定性計算と決定性計算の違いはわりと繊細なのかもしれません．
  • 理論的に順を追って考えると理解出来るが、直感的にわかるような問題でなくなってきたので難しい。
    --計算理論というのはわりと抽象的なのですが，抽象的な思考に慣れることはとても重要なので，勉強して，慣れていってください．
  • 時間階層定理と領域階層定理の証明法が似ているのに対し、非決定性時間階層定理の証明は全く異なることが以外に思った
    --非決定性階層定理の証明についてはまったく述べませんでした．証明で使われる論法のひとつに「遅延対角線論法 (delayed diagonalization)」というのがあります．興味があれば調べてください．
  • 先生が公開されている講義資料だったか，先生が寄稿された雑誌の記事だったか忘れましたが "「計算」について未解明なことが本当にたくさんある" という旨の言及を見た記憶があって，今までも「そうだよな」と思っていたのですが，今日の講義を聞いてますますそう思えてきました．誰も知らないことを新たに明らかにするという意味で，調べる価値があることがいっぱいあると思えるのは嬉しい反面「計算」がどれだけ途方もなく深遠なものであるのかと感じます．
    --結局，人類は「計算」に関する理解が乏しいのだと思います．そもそも計算がなんであるのかというコンセンサスも無いように思います．この授業ではチューリング機械を (暗に) 計算モデルとして採用していますが，「世の中のありとあらゆる計算を統一的に記述できる計算モデル」というのはまだ無いように思います．それだからこそ，物理学における「宇宙の起源はなにか？」とか生物学における「生命とはなにか？」とか哲学における「人間とはなにか？」のような問いがコンピュータサイエンスにおいても「計算とはなにか？」という形であって，科学としてコンピュータサイエンスを研究する必要があると思っています．
  • 次回難しい範囲ということで気合い入れて頑張ります。
    --すみません，怖がらせすぎているかもしれません．できるだけ分かりやすくなるように，私も努力します．
  • 証明などが多く授業中だけで理解するのが難しくなってきたので授業動画を見返して復習しようと思います。
    --はい，動画を活かしてください．
  • 証明や新しく聴く概念が多く難しいかったです。復習します。
    --はい，前に出てきた内容が再び突然現れることがあるので，ぜひ復習をしてください．
  • 授業の内容はしっかり理解できたとは言えないレベルなので要復習ですが、クイズは優しいので助かってます。
    --はい，クイズは優しく，易しくしているつもりです．正答率90％ぐらいを目指しています．
  • 今回は4番がアニメと関係なく，少し悲しかったです．
    --期待は裏切られるものなのです．;-)
  • 単位時間あたりの理解度を最大化出来る動画再生速度はどれくらいなのかいつも試行錯誤しています。自分の理解力が平均より高いという過信で1.25倍にして失敗するようなことが多いです。
    --これは難しいですね．一度だけ見てすべてを理解しようとする必要はないのかもしれないので，失敗したと思ったら，繰り返して見ればよいと思います．
  • 倍速で聞こうとすると､聞き流す形になり頭に入ってきません。倍速できくコツを教えてください。
    --私は，YouTubeだと字幕をonにします．英語はわりと正確に自動字幕をつけてくれます．もちろん正しくないところもありますが，それでも目と耳の情報が補完しあって理解しやすくなるように感じています．
  • 先生の授業、普通の授業動画を1.5倍速してるようなしゃべりスピードだなと思いました。私は聞き取りやすくてわかりやすいと思います。
    --遅すぎると，むしろ分かりにくくなるとは思っています．
  • 先週から暑い日が続いて大変です。
    --そうですね．ご自愛ください．
  • 最近暑すぎます
    --週末はまた寒くなるそうですので，気を付けてください．
  • 今日は最高気温が32度予報なのに、木曜と金曜の最高気温は19度で体調が崩れそうな天気ですね。先生も体調には気を付けてお過ごしください。
    --そうですね．お互いに気を付けましょう．
  • 冬が終わったと思ったら、もう暑い。春・秋服の出番を知りたい。
    --「四季ではなく二季」と呼ばれる現象ですね．ただ，日本には桜と紅葉がありますから，短くても春と秋は感じられるのではないかと思います．
  • 最近暑すぎです。この暑さで梅雨が来てしまうと耐えられる気がしません。先生は寒いのと暑いのはどちらの方が苦手ですか。
    --寒いのは着ればよいので，なんとか寒さは凌げる気がしています．しかし，暑いといっても脱ぐには限界があるので，暑さを凌ぐのは大変で，夏は保冷剤を体のいろいろなところに当ててます．
  • 最近暑すぎです。この後に梅雨がきて耐えられる気がしません。先生は暑いのと寒いのではどちらの方が耐えられますか。
    --寒いのは着ればよいので，なんとか寒さは凌げる気がしています．しかし，暑いといっても脱ぐには限界があるので，暑さを凌ぐのは大変で，夏は保冷剤を体のいろいろなところに当ててます．
  • 鼻血が出て鼻にティッシュを詰めたら取れなくなって病院に行きました．カメラで深さ優先探索してもらったのですが見つかりませんでした．おそらくティッシュを抜いたことを忘れていたものと思われます．行く病院を間違えました．
    --状況がよく分からないです (-_-;．ティッシュを抜いたのは誰で，それを忘れていたのは誰なのでしょう？
  • そろそろ就活をちゃんと始めなきゃと焦っています
    --焦らなくても，始めればよいのです．ぜひ始めてください．
  • 無し
    --はい，前と同様に0.5点はありませんので，ご了承ください．
• 5/12 (5) 時間と領域の関係：P⊆PSPACE⊆EXPTIME
  • ないです
    --はい，コメントがない場合は0.5点もないので，その点はご了承ください．
  • 最近暖かくなってきましたが朝はまだ肌寒いですね．体調に気を付けて過ごしてください．
    --ありがとうございます．お互いに気を付けましょう．
  • 週末には30℃を超える日が出てくるみたいです。熱中症の方が出てきてニュースになりそうですね。
    --暑い日もあるので，注意したいですね．
  • GWが恋しいです
    --7月にまた連休がきますよ．
  • ゴールデンウイークが終わってしまい、五月病になりそうです。やる気を出さねば。
    --やる気を出そうと思って出すと，疲れてしまいそうです．徐々に慣れていけばよいと思います．
  • カルビーのポテチの袋が白黒になるのが悲しい
    --色がなくなって目立たなくなると，売れなくなりそうです．一方で，白黒の方が目立つ可能性もあって，それで目立って売れるようになるということもある気がします．いずれにせよ，白黒になるということでいろいろなニュースに取り上げられたので，宣伝効果はかなりあったと思います．
  • 先日私のバイト先の飲食店に、岡本先生の研究室を卒業された方が偶々来店されました。世間は意外と狭いものなのかなと思った瞬間でした。
    --たしかに世間がせまそうですね．;-)
  • 今回の問題を解いて、計算量クラス同士の包含関係がどのように証明されるのかを理解できた。特に、P ⊆ PSPACE では多項式時間で計算できる問題は使う領域も多項式に抑えられること、NP ⊆ PSPACE では非決定性計算も決定的にシミュレーションできることが分かった
    --そのとおりですね．正しく理解できていると思います．
  • 具体的な問題を用いた証明だったため分かりやすかったです。
    --いわゆる「方針2」の方ですね．私もこちらの方が分かりやすいと思います．今後の授業でも頻繁に登場します．
  • 時点状況の数え上げや水増し論法といった手法は、複雑性クラス間の包含関係を証明するのに強力な手法だとわかりました。
    --そうですね．時点状況を考えて議論するという手法は，計算理論においてよく出てくるので，ぜひ身につけてください．
  • 新しいクラスが登場(？)する度にほかの全てのクラスとの関係を調べなくてはいけないのは少し大変だなと思った
    --はい，これは大変です．そうであっても，基本的なことなので，しっかりと行っています．
  • クラス関係のつながりに対して、再び驚いて面白くなった。
    --面白く感じてもらえるのは，うれしいです :-)
  • P=NP問題は知っていたが，EXPTIME=NEXPTIME問題は知らなかった．
    --過去の授業では他の未解決問題も述べているので，ぜひ見直してください．
  • 計算複雑性は名前や記号が多く、それぞれの関係を完全に整理しきれていない部分もあるため、今後は復習を通して時間計算量と領域計算量の違いや各クラスの位置づけを改めて整理し、理解を深めていきたい。
    --はい，復習をお願いします．ただ，覚える必要はないと思ってください．忘れたときに調べて思い出せるようにしておくのが大事だと思います．一度勉強していれば，思い出しやすくなると思います．
  • ＝の証明が楽しみになりました。
    --はい，これは後の方の授業の内容となります．お楽しみに．
  • 用語の使い方や表現等、都度丁寧に修正されていて私も見習わなければと思いました。研究者志望として無頓着に記述してしまうことがある悪癖を治したいです…
    --一応，ことばは大事にしているつもりです (うまくできているかどうかは自信がないですが)．言葉はコミュニケーションのもっとも重要な構成要素のひとつなので，うまく伝えたり，正しく理解するためには，大事にする必要があると思っています．
  • 資料が整頓されててすごく見やすいです！
    --ありがとうございます．分かりにくいところや整頓されていないと思うところがあれば，ぜひ教えてください．
  • P=NP → EXPTIME=NEXPTIMEの対偶をとると、EXPTIME≠NEXPTIME → P≠NPなので、等価でないことを示すならばP≠NPのほうが簡単なのではと思った。
    --はい，そのとおりですね．授業では「P=NPを示そうと思うなら，EXPTIME=NEXPTIMEを示そうとするほうが簡単」のようなことをいったと思います．P=NPを信じるのかP≠NPを信じるのかという立場によって何をするべきなのかが変わるのでしょうね．
  • 「P = NP ⇒ EXPTIME = NEXPTIME」の対偶は「EXPTIME ≠ NEXPTIME ⇒ P ≠ NP」になるので，NEXPTIMEに属する何かしらの問題がEXPTIMEに属さないことを示せれば，P≠NPが証明できるのだと考えました．この方針で解こうとしている研究があるのか，調べてみたいです．
    --その方針で考えている研究を私は知りません．ぜひ調べてみてください．
  • P=NPかつEXPTIME≠NEXPTIMEのことはない、とのことなので、先にEXPTIME=NEXPTIMEが成り立つかどうかを調べてP≠NPなのかP=NPなのかはっきりさせるのはありなのではないか、と思った。
    --ありなしでいえば，ありですね．そのとおりだと思います．
  • 水増し論法についての説明がわかりやすかった。領域複雑性が少し苦手に感じるので前回分から復習したい。
    --領域複雑性や非決定性には慣れが必要かもしれませんね．ぜひ復習してください．
  • 水増し論法の説明が分かりやすかったです。
    --ありがとうございます．
  • 水増し論法を初めて知ったので面白かった．次回の対角線論法も厳密にはわかっていないので，とても楽しみです．
    --対角線論法を厳密に扱うわけではないので，あくまでも雰囲気になってしまいます．その点はご了承ください．ただ，それでも，対角線論法の理解が深まればよいな～と思っています．
  • 水増し論法のbが複雑性を大きくするのに利用されるのは自分の直感的には変な感じがしたものの，面白い考え方だった．
    --直感的には変だという感じは正しいと思います．ただ，形式的には正しいのです．このあたりが計算という現象の面白いところでもあると感じています．
  • 入力を増やしてクラスを変えるということが出来ていることに何か違和感を感じた。
    --そうですよね．まず，このような論法があることを理解してください．
  • 無意味なデータを付け加える水増し論法は，それで証明が成立してしまうのがなんだか不思議な気がしました．
    --はい，私も不思議に感じています．おそらく，まだしっかり理解できていないのだと思います．
  • 水増しという単語を初めて悪い意味合い以外で目にしたと思う
    --たしかに ;-)
  • 水増し論法が妥当な論法であることを，きちんと確認するには，入力の符号化から真面目に扱わないといけない（この講義では扱わない）とおっしゃっていましたが，符号化の段階（つまり，問題を形式言語として扱うところ）からきちんと考えて，水増し論法が妥当であることを解説しているような情報源って何かご存じでしょうか．
    --書籍でいえば，下に挙げてある荻原先生の本や守屋先生の本にはちゃんとした説明 (証明) があります．ただ，荻原先生の本では「パディング法」と呼んでいて，守屋先生の本では「詰め込み論法」と呼んでいるので，注意してください．
  • 水増し論法、説明もわかりやすくて理解はできたと思うのですが、なんとも言えない気持ちになりました。
    --なんとも言えない気持ちになりますよね．私もだまされたような気持ちになっていますし，だましたような気持ちになっています．
  • 水増し論法が輪行で取り扱う内容だったので先取りできてよかったです
    --それはよかったです．しっかりと理解してください．
  • セブンイレブンで一部の商品50%増量キャンペーンが始まっています。想像以上に大きいのでおすすめです。
    --これを水増し論法といってしまうと，怒らせそうですね．;-)
  • 今回のクイズの4番の元ネタは調べるまで分かりませんでした。
    --調べる必要はありませんので，あしからず ;-)
  • 毎回，選択肢にアニメなどの要素が入っていて，クスっとしています．自分は熱いのが嫌いなので，最近熱くなってきて残念です．
    --3つも誤答選択肢を思いつけないのです…．
  • 毎回4番がちょっと楽しみです。
    --これはこれで，わりと考えているのです．:-)
  • クイズの選択肢の一つが毎回面白いなと思っています。今回ジョジョがらみの選択肢で特に好きでした。
    --気に入ってもらえて，よかったです．
  • ジョジョ嬉しいです。
    --うれしく思ってもらえてよかったです．
  • 僕は6部が好きです！！
    --私は岸辺露伴の実写ドラマを見たことしかありません．
  • Dio のように時を止めたいです。もし、時を止めることができたら先生は何をしますか。僕は、いっぱい寝ます。
    --時を止めても自分に流れる時間は変わらないので，普通通り生活するのではないかと思います．むしろ自分以外が止まっているので不便である可能性すらありそうです．
• 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のフォームで行います．
• レポート課題1

• こちらをご覧ください

• 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, 3rd Edition, Course Technology Inc, 2021. (邦訳あり)
• Sanjeev Arora and Boaz Barak, Computational Complexity Theory: A Modern Approach. Cambridge University Press, 2009.
• Dexter C. Kozen, Theory of Computation, Springer, 2006.
• Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
• Christos Papadimitriou. Computational Complexity. Addison Wesley, 1994.
• 守屋哲朗，チューリングマシンと計算量の理論，培風館，1997．
• 荻原光徳，複雑さの階層，共立出版，2006．

• Complexity Zoo