離散最適化基礎論

岡本 吉央

テーマ：離散最適化における計算困難性

注意：内容は毎年変わります

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

講義資料

• 1/21 (13) アルゴリズム的問題解決：再考
  • 前回の残りからやります
  • スライド | 印刷用スライド
• 1/14 (12) 文字列に関する問題
  • スライド (1/14修正) | 印刷用スライド (1/14修正)
• 1/7 (11) 計算幾何学に関する問題
  • スライド (1/13修正) | 印刷用スライド (1/13修正)
• 12/17 (10) 平面性が関わる問題
  • スライド (12/17修正) | 印刷用スライド (12/17修正)
• 12/10 (9) 数値が関わる問題 (2)：3分割問題
  • スライド (12/11修正) | 印刷用スライド (12/11修正)
• 12/3 (8) 数値が関わる問題 (1)：2分割問題
  • スライド | 印刷用スライド
• 11/26 (7) 集合族に関する問題 (2)：発展
  • スライド (11/26修正) | 印刷用スライド (11/26修正)
• 11/19 (6) 集合族に関する問題 (1)：グラフとの関連
  • スライド (11/19修正) | 印刷用スライド (11/19修正)
• 11/12 (5) グラフに関する問題 (2)：経路の選択
  • スライド (11/16修正) | 印刷用スライド (11/16修正)
• 11/5 (4) グラフに関する問題 (1)：部分集合の選択
  • スライド (11/24修正) | 印刷用スライド (11/24修正)
• 10/29 (3) 充足可能性問題とその変種
  • スライド (10/31修正) | 印刷用スライド (10/31修正)
• 10/15 (2) 速習 P vs NP問題
  • スライド (11/24修正) | 印刷用スライド (11/24修正)
• 10/8 (1) アルゴリズム的問題解決と計算複雑性
  • スライド (10/16修正) | 印刷用スライド (10/16修正)

• 1/21 (13) アルゴリズム的問題解決：再考
  • コメントをありがとうございました．「やり残したところから再開」という文言を無視してしまいました．すみません．その部分は自習して下さい．
  • 半年間ありがとうございました
    --- こちらこそありがとうございました．
  • 半年間ありがとうございました。
    --- こちらこそありがとうございました．
  • 半年間ありがとうございました．
    --- こちらこそありがとうございました．
  • 毎回コメントに対して丁寧に返して下さるのですが、そのモチベーションはどこから沸いてくるのでしょうか？
    --- これが私の生きがいだからです :-)
    丁寧かどうかは皆さんが判断することであって，私が丁寧だと思っているかは重要ではないです．なお，このコメントページは自称「業界注目度ナンバーワン」なので，ご注意ください ;-)
  • P=NP問題は聞いたことがあったのですが理解できてなかったものなのですがこの授業を受けて少し分かった気がしました．とてもおもしろかったです
    --- 何かのお役に立てたようで，よかったです．ありがとうございました．
  • 計算複雑性の深い部分まで取り扱っていて興味深かった。
    --- 何度か言ったり書いたりしたのですが，今一度強調すると，この講義は「計算複雑性」の講義ではありませんでした．計算複雑性の理論をどのように使うのか，という話を1学期間してきたつもりです．もちろん，そのためには計算複雑性の理論をある程度理解する必要がありますが，計算複雑性自体を深く議論したつもりはありませんでした．計算複雑性の深い部分は計算複雑性の本や講義でぜひ勉強して下さい．;-)
  • 制限アプローチに関して、
    マッチングの最大要素数 ≦ 頂点被覆の最小要素数
    が等号で成立するグラフであれば多項式時間で解けることになると思いますが，そのようなグラフは二部グラフ以外には見つかっているのですか？
    --- 鋭い質問ですね．
    そのようなグラフは二部グラフ以外にもあります．例えば，次のグラフです．
    
    「マッチングの最大要素数＝頂点被覆の最小要素数」を満たすグラフには名前が付いていて，Kőnig-Egerváryグラフと呼ばれています．名前はもちろん二部グラフに対するKőnigとEgerváryの定理にちなんでいます．
    それで，「マッチングの最大要素数＝頂点被覆の最小要素数」を満たすグラフ，つまり，Kőnig-Egerváryグラフに対して最小頂点被覆問題が多項式時間で解けるのか，と問われると，実際解けるのですが，これには少し注意が必要です．講義で行った論法を使うと，多項式時間で分かるのは，「頂点被覆の最小要素数」という数値であって，そこから「最小要素数の頂点被覆」という集合を見つけるには，もっとステップを踏む必要があります．(スライドでは「第1回講義参照」と書いてあるところです．) しかし，ここからは組合せ最適化の深い議論 (といっても，組合せ最適化としては基本的な議論) を用いるのですが，線形計画法を用いると，最小要素数の頂点被覆が多項式時間で見つかります．これは，いわゆる「多面体の整数性」とかそういう話題とつながっているのですが，これをここで語るのは骨が折れるので，やめます．
  • 計算資源の限られているスマートフォンなどの普及を考えると、制限アプローチや近似アプローチの研究に人気が集中しそうな気がしますね．
    --- そうですね．昔の話をすると，例えばファミリーコンピュータ (初代ファミコン) が積んでいたのは8ビットCPUで，2kバイトのワーキングRAMだったようです．それで世界中が熱狂するようなゲームを設計していたわけですから，相当苦労があったと思います．
    最近の話をすれば，計算資源が限られる重要なケースとして挙げられるのは，いわゆる「組み込みシステム」です．ただ，最近は何でもクラウドで行うようになってきていて，計算資源よりも通信資源の方がボトルネックになっている気がします．
    ここで重要なことをいいますが，通信資源を見積もるということは，最先端の計算複雑性の理論で極めて重要なトピックであり，盛んに研究されています．計算と通信は切っても切れない関係を持っているのです．
  • 2⁸ = 256に対し 1.618⁸ ≦ 47 なので あの枝刈りはかなり効率がいいということが実感できた．
    --- そうですね．ただ，1.618ⁿというのは理論的な最悪時実行時間なので，実践的にはこの見積よりも高速だと思います．
  • 枝切りで再帰の木が小さくなる図はどのように作ったのですか？自動生成？
    --- これは手作業で描いてます．手作業で再帰をしています．
  • 工夫した厳密アプローチの計算量解析はなにかと大変な印象がありますが実際どうなのでしょうか
    --- 実際，これは大変です．一方で，この手のアルゴリズムの最悪時実行時間を自動的に導く方法も開発されています．いくつかの論文では，この方法で計算量の解析をしています．
• 1/14 (12) 文字列に関する問題
  • コメントをありがとうございました．次回が最終回となります．今回やり残したところから再開します．
  • 次回最終回なんですか。早かったですね。
    --- そうですね．(^^;
  • まだ寒いですね....体調にお気をつけください。
    --- お気遣いありがとうございます．皆様もご自愛ください．
  • レポートの平均点はどのくらいでしたか？
    --- まだ採点ができていません．
  • 部分文字列と部分列 混同しがち
    --- 「文字列あるある，早くいいたい」でしょうか？
  • 距離にもいろいろありますね．
    --- そうですね．世の中には『Dictionary of Distances』とか『Encyclopedia of Distances』というものがあります．これを見てると，なんかワクワクしてきます．
  • 定理と事実の違いって，なんですか．
    --- 数学的には，違いがありません．違いは「気持ち」にあります．
    授業で「定理」と呼んでいるものは，その授業の中のメイントピックとなるものです．一方，「事実」は，知られていることをただ述べているだけ，だと思って下さい．
  • なし
    --- ありがとうございます．
  • 特にないです
    --- ありがとうございます．
  • 特になし。
    --- ありがとうございます．
• 1/7 (11) 計算幾何学に関する問題
  • コメントをありがとうございました．
  • なし
    --- ありがとうございます．「なし」でもよいので，この紙は出し続けて下さい．
  • あけましておめでとうござます．ことしもよろしくおねがいします．ねずみ年ですね．
    --- ござます．
  • レポートの点数が気になります．連絡をすれば教えていただけるのでしょうか？
    --- すみませんが，まだ採点が済んでいません．採点ができたら，メールで個別にお送りします．
  • 今回の講義の印刷スライドでいちばん時間がかかったのはどれですか？
    --- 単位円の中心を求める計算です．
  • 幾何になると大小比較さえも難しい場合があると実感しました．
    --- そうですね．私たちが計算しているつもりでいることには，いろいろな近似であるとか，不正確さであるとか，そういうものが混ざっているのです．それを意識できるかできないか，ということは，ただプログラムが書ける人と，背景知識を持っているプログラマの大きな違いだと思います．
  • スライド12ページで述べた観察は一般に成り立つ事実なのですか
    --- 「一般」が何を指すのか依存しますが，「一般の単位円」で成り立ちます．証明は図に描いてあることを書き下すことでできます．
  • 集合恐怖症には優しくないスライドだった．(そんなことを言いだしたら今までのほとんどのスライドもそうですけれど)
    --- それは失礼しました．しかし，どのように回避すればよいのか，よいアイディアが浮かびません (-_-;
• 12/17 (10) 平面性が関わる問題
  • コメントをありがとうございました．レポート課題1の提出締切は12月25日です．忘れないように，よろしくお願いします．
  • よいお年を．
    --- よいお年を :-)
  • レポートはLaTEXなどで書いた方が良いのでしょうか？ (手書きのものをスキャンしてPDF化は不可？) よろしくお願いします
    --- 「手書きのものをスキャンしてPDF化」でも構いません．丁寧に書いて下さい．
  • 年末で色々やることが多くてたいへん...。
    --- 「せわしない師走」なのか「せわしい師走」なのか．
  • 図を十分に描き込んでいないと発表時に後悔するという教訓が得られた．
    --- 確かにそうですね．私も教訓を得ました ;-)
  • 特にないです
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 難しい
    一年経ったらキレイさっぱり忘れていそう..
    --- 覚えなくてもよいです (私も覚えていません)．まずは，このような考え方がある，ということを理解して下さい．そして，必要となったときに，調べて思い出せれば問題ありません．
  • 平面的3-SATというのは先生の造語ですか？
    --- もとの英語は「planar 3-SAT」で，これはよく使われる用語です．「planar」は「平面的」と訳すことが多いので，「planar 3-SAT」を「平面的3-SAT」と訳しました．
  • G=(V, E) が与えられてそれが平面的グラフかどうか判定って可能ですか
    --- これはいわゆる「グラフの平面性判定問題」とか「平面的グラフの認識問題」と呼ばれるもので，よく研究されています．結論からいうと，多項式時間で解けます．グラフを隣接リストで入力するときには，線形時間で解けます．
  • 交差解消ガジェット．よく思いつくなあと感心した．
    --- これを思いつくのは，なかなか大変だと思います．最近では，コンピュータを使って探索をすることで，ガジェットを発見するという手法もよく用いられています．
  • ガジェットを考えるの、最高の暇潰しになりそうだと思いました。実際、出来た時の気持ち良さが大きそうです。
    --- 実際に，出来たときは気持ち良いです :-) 私の個人的経験によると，NP完全性の証明はヒラメキで出てくることが多いです．
• 12/10 (9) 数値が関わる問題 (2)：3分割問題
  • コメントをありがとうございました．次回が年内最後になります．
  • 特になし。
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • なし
    --- ありがとうございます．「なし」でもよいので，この紙は出し続けて下さい．
  • 特にないです
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 特になし
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • レポート課題難しい
    --- しっかりと考えて下さい．
  • レポート課題は何時間ぐらいで解ける想定ですか？
    --- 想定は何もないです．おそらく，分からなければ，どれだけ考えても分からないでしょうし，分かるならば，そのうち分かると思います．
  • 図が多くて分かりやすいです。
    --- 図を描くことには，力を入れています．一方，レポート課題には「意図的」に図を描いていません．自分で描いてみるようにして下さい．
  • binをみたとき，「2」を思い出したけど違った．
    --- なるほど，そういう連想もありますね ;-)
  • 最適化問題と判定問題は自由に書き換えができますか．
    --- これは第1回の講義で扱っているので，そちらを復習してみて下さい．この講義で扱う範囲の問題では，自由に書き換えができると考えてもらってよいです．
  • ・回転するとNo入力がYesになってしまう
    ・計算は多項式時間でできるが入力が多項式時間でない
    など少し気をつけなければならない盲点が多いと感じました．
    --- そうですね．本来はいろいろな証明をまじめにやらないといけないのですが，この講義では，割と雰囲気で流しています．
  • 長方形への長方形の充填問題の帰着について，幅を伸ばすことで回転を許さないようにしていましたが、逆に高さを伸ばすことで対処できる気がしました．
    
    --- そうですね．講義で紹介した帰着は1つの例ですので，もちろん，他の方法はあると思います．これはこの講義で紹介しているどの帰着についても言えますので，いろいろな問題に対して，講義で紹介した帰着とは異なる帰着を考えてみて下さい．
  • 箱詰め問題で計算機上で表せる座標平面上の数は有限なので、計算機上でNoを出力しても実際にはYesであることがある気がした。
    --- たぶん「箱詰め問題」ではなくて「長方形の充填問題」のことを指していると思うので，そうだと思ってコメントします．
    実際にそういうことはありえますし，あります．そのため，問題を引き起こすことがあります．もっと大きな問題は，計算機上でYesを出力するのに，実際にはNoである場合におきます．それが起きると，プログラムの出力どおりに積み込むことができないことになります．そのため，我々は数値計算やいろいろな種類の誤差の影響をまじめに考える必要がありますし，それを克服する技術を開発する必要があるのです．
• 12/3 (8) 数値が関わる問題 (1)：2分割問題
  • コメントをありがとうございました．レポート課題1を出題しました．提出締切は12月25日ですので，よろしくお願いします．
  • なし
    --- ありがとうございます．「なし」でもよいので，この紙は出し続けて下さい．
  • 特になし
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 特になし．
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 特になし
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 特にないです
    --- ありがとうございます．「特にないです」でもよいので，この紙は出し続けて下さい．
  • 授業ありがとうございます
    --- こちらこそありがとうございます．
  • レポート頑張ります！
    --- すごい気合ですね ;-)
  • 最近寒いです．
    --- そうですね．風邪ひかないようにご注意ください．
  • 寒くなって朝起きることができなくなってしまっている
    --- 20年ぐらいは生きているわけですから，もうそろそろ慣れて下さい．
  • まだエアコンを稼働させてなかったのですが、夜さむすぎるのでそろそろつけます．
    --- 加湿機を併用するとよいかもしれません．
  • 2と3の違い よんでみますね。
    --- はい，ぜひどうぞ．:-)
  • レポート課題をみてふるえた
    --- しっかりと取り組んで下さい．
  • 整数が入力のときに時間が変わるのはなるほどと思いました
    --- そうですね．あまり気付かれていないことかもしれないのと思ったので，今回の授業で扱いました．
  • 2進法と1進法による入力があれば、3進法、m進法が考えられそうですが、2進法のときと差があまりなさそうな気がしてきました．
    --- 例えば，3進法の場合，自然数 $n$ を表すのに必要な桁数は$\log_3 n$ ぐらいになります．これはオーダー $\log n$ なので，2進法で表す場合の桁数とオーダーが変わりません．この意味では「2進法のときと差があまりない」と言えます．
    その一方で，「自然数 $n$ を $\log_2 n$ 進法で表す」ということに似たことをする場合があります．これを使って，アルゴリズムの計算量を小さくするという技法があります．
  • 2分割問題の入力集合 $A$ について，
    • $A$ の要素が実数になる場合
    • $A$ が無限集合の場合
    では問題の難しさが変わるのでしょうか．
    --- まず，「実数をどのように入力するか」とか「無限集合をどのように入力するか」ということをまじめに考える必要があります．
    実数の方から言いますと，現在のデジタルコンピュータ，あるいはそれを数学的に抽象化したチューリングマシンやランダムアクセスマシンで，任意の実数を入力する方法はありません．これは，自然数全体の集合 $\mathbb{N}$ と実数全体の集合 $\mathbb{R}$ の間に全単射が存在しないことから分かります (対角線論法)．そのため，入力できる実数に対して，ある程度の制限を設ける必要があります．
    (念のために書いておくと，「実数を入力する」ということと「浮動小数点数を入力する」ということは，根本的に異なることです．浮動小数点数の加算は結合法則を満たしませんし，その他にも，実数の持っているよい性質の多くを持ちません．)
    もっとも簡単な制限 (で自然数よりも対象を大きくできるの) は有理数だけを考えるというものです．有理数は2つの整数 $p, q$ の比 $p/q$ として表されるので，$p$ と $q$ を符号化すれば，$p/q$ も符号化できます (例えば，C言語で，有理数の構造体を作るとき，メンバ変数を分子と分母に対応する整数とする，ようなことを連想して下さい)．有理数 $a_1,\ldots, a_n$ を入力とする2分割問題では，$a_1, \ldots, a_n$ の分母の最小公倍数を $a_1,\ldots,a_n$ に掛けると，その結果はすべて整数になり，Yes/No入力であるという性質も保存されます．つまり，この場合は，整数を入力とする2分割問題と，難しさは変わりません．
    もう少し難しい制限は正有理数の平方根までは許す，というものです．この場合も符号化はできます．
    さて，この場合，そのような数が複数あるとき，例えば，$a_1,\ldots, a_n$ と $b_1,\ldots,b_n$ があるとき，$a_1 + \cdots + a_n$ と $b_1 + \cdots + b_n$ が等しいかどうかを調べることは自明ではなくなります．しかし，これは多項式時間でできることが知られています (Blömer '91)．これを使えば，この場合の2分割問題もNP完全であることが分かります．
    このように考えるべき数の集合を大きくしていくと，「その数をどのように符号化できるのか」ということと「和をどのように比較するのか」ということを考える必要がでてきて，問題は難しくなりがちになります．
    次に，無限集合の方です．無限集合を有限の記述で表し，それを入力とすることを考える必要があるので，必然的に，入力できる無限集合の姿は限られます．また，無限和を考えることになるので，その収束性も問題になります．そのため，意味のある問題とするためには，いろいろな工夫 (あるいは注意) が必要となるでしょう．この場で，私には思いつきません．
    
  • 弱NP困難でなくとも，弱多項式時間で解けない．そのような問題は発見されていますか．
    --- 弱NP困難であるとも証明されておらず，弱多項式時間アルゴリズムも知られていない問題ならあります．例えば，素因数分解です．(ただし，素因数分解問題は判定問題ではないので，それには注意して下さい．) あるいは，Ladnerの定理によれば，P≠NP ならば，NP完全でもなく，多項式時間でも解けない問題が必ず存在します (具体例は知られていません)．
• 11/26 (7) 集合族に関する問題 (2)：発展
  • コメントをありがとうございました．
  • なし
    --- ありがとうございます．「なし」でもよいので，この紙は出し続けて下さい．
  • 特になし
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 特になし
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 特にないです
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • 最近寒くなってきてかぜをひきました．先生も体調に気をつけてください...
    --- お大事に．
  • 寒さがきびしくなってまいりました．
    --- そうですね．冬っぽくなってきましたね．
  • めっちゃ寒くなりましたね．
    --- そうですね．冬っぽくなってきましたね．
  • 調布祭、研究室はどうでした？
    --- たくさん，特にお子様がいらっしゃいました．調布祭パンフレットを見たのですが，そこに掲載されている研究室が割と少ないことに驚きました．これはおそらく教員の責任なので，調布祭パンフレットに研究室公開の広告を載せるよう，教員に働きかけるとよいと思います．たくさんの方に来ていただくためには，調布祭パンフレットの掲載を重視するとよいと思います．
  • Pメロディアン問題
    入力：実数 k, m, n
    出力：Yes, No
    条件：メロディアンの商品「甘酒」の円柱型容器 (底面半径 k) を，m×n 長方形の冷ケースにおさめることができるか．
    --- 「P」は何なのですか？ ;-)
  • 集合被覆問題がシュタイナー木に帰着可能することは思いもよらなかった．
    --- この帰着はよく知られていると思うのですが，どの論文がはじまりなのか，調べてもよく分からなかったです．GareyとJohnsonの本には，違う帰着が書いてあります．
  • シュタイナー木問題で $|R|$ が $|V|-\ell$ と $\ell$ で場合分けしていたが $|V|-\ell=\ell$ となる場合などがありなぜ分けるかが分からない．
    --- その部分は説明不足だったと思います．すみません．これは場合分けではないのです．今一度，説明しようとしてみます．
    そこでは，$|R|$ の値によって，シュタイナー木問題が簡単になる，ということを説明したかったのです．
    $|R|$ の値は，0から $|V|$ の間にあります．$|R|$ が0や1の場合は，問題として面白くないので，除外します．$|R|=2$ のとき，シュタイナー木問題は最短路問題になり，多項式時間で解けます．では，$|R|=3$ であったり，$|R|=4$ のときにも多項式時間で解けるのか，ということが気になります．答えは「Yes」です．つまり，$|R|=3$ であったり，$|R|=4$ のときも多項式時間で解けます．より一般的に，$|R|$ がどんな定数であっても多項式時間で解けます．その定数を $\ell$ とすると，「$|R|=\ell$ のときにシュタイナー木問題は多項式時間で解ける」と分かることになります．
    もう一方の極端を考えると，$|R|=|V|$ の場合になります．このとき，シュタイナー木問題は全域木問題になり，多項式時間で解けます．では，$|R| = |V|-1$ であったり，$|R|=|V|-2$ のときにも多項式時間で解けるのか，ということが気になります．答えは「Yes」です．つまり，$|R|=|V|-1$ であったり，$|R|=|V|-2$ のときも多項式時間で解けます．より一般的に，$|V|-|R|$ がどんな定数であっても多項式時間で解けます．その定数を $\ell$ とすると，「$|R|=|V|-\ell$ のときにシュタイナー木問題は多項式時間で解ける」と分かることになります．
    $|V|-\ell=\ell$ のとき，つまり，$\ell = |V|/2$ のとき，$|R|=\ell$ であっても，$|R|=|V|-\ell$ であっても，$|R|=|V|/2$ となります．このとき，シュタイナー木問題 (判定問題版) はNP完全になります．これは授業で紹介した帰着を少しいじると証明できます．$\ell = |V|/2$ のとき，$\ell$ の値は入力のグラフによって変わることに注意して下さい．つまり，このとき $\ell$ が定数ではないのです．
  • 2と3の違いであったり，3と4の違いであったり，たった1つの違いで難しさが大きく変わるのが面白いと思った．
    --- 私もそう思います．この観点については，私が以前 「2と3の違い」(PDF) という記事を書きました．興味があれば，ご覧ください．
• 11/19 (6) 集合族に関する問題 (1)：グラフとの関連
  • コメントをありがとうございました．
  • 特になし
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • なし
    --- ありがとうございます．「なし」でもよいので，この紙は出し続けて下さい．
  • 特にないです
    --- ありがとうございます．「特にないです」でもよいので，この紙は出し続けて下さい．
  • 特になし．
    --- ありがとうございます．「特になし」でもよいので，この紙は出し続けて下さい．
  • もうすぐ調布祭ですね．何かとくべつな準備はしましたか？
    --- 楽天西友ネットスーパーで注文をしました (^^;
  • 岡本先生のフルネームを全て漢字で書くと線対称ですね
    --- よく言われます ;-)
  • スライドのオイラー図は何のソフトウェアで作成しているのですか
    --- Ipeです．
  • 講義の準備 (時間，手間) 毎回大変そうですね．グラフとか．
    --- 皆さんもセミナーなどの準備に時間と手間をかけてください．
  • 3-SATを集合分割問題に多項式時間多対一帰着するのに使った図をつくるのが大変そう
    --- 実をいうと，これは線を引いてるだけなので，あまり大変ではないです (といっても時間はかかってますが)．むしろ，頂点被覆問題を集合被覆問題に多項式時間多対一帰着するときに使った図の方に時間をかけています．この図では，集合族を表す図の線が，もとのグラフの辺を表す線と平行になるように細かい調整をしています．また，異なる集合を表す線が重ならないように，幅を細かく変えたりしています．そのような調整に時間がかかっています．
  • グラフに関する問題の問題例として与えているグラフがいつも同じで驚く。万能グラフと名付けよう．
    --- 実は，ちょっとずつ変化している可能性があるので，ご注意ください．
    なお，「万能グラフ (universal graph)」という概念がグラフ理論にあります．
  • 3-SATからの帰着はやはり難しかった．
    --- Karpの論文には3彩色問題を帰着する方法が書いてあるのですが，3-SATを帰着する方が図を描きやすいと思いました．また，今後の話の流れもこちらの方がよさそうだと思い，3-SATを帰着する方法を紹介しました．
  • ガジェットを考え付いた人は頭が良いなと思いました
    --- 慣れてくると思いつくようです．
  • 帰着って難しいですね。
    --- それだから，研究になるわけですね ;-)
  • グラフのマッチングと密接に関わりのある集合族の問題は何かありますか？
    --- グラフのマッチングは集合充填問題の特殊な場合になっています．つまり，マッチング問題は集合充填問題に (自然に) 多項式時間多対一帰着可能です (頂点被覆問題を集合横断問題に帰着したときに用いた構成法をそのまま使えばよいです)．しかし，マッチング問題は多項式時間で解けるので，これでは集合充填問題のNP完全性は証明できません．マッチングについては，次回少し登場する予定です．
• 11/12 (5) グラフに関する問題 (2)：経路の選択
  • コメントをありがとうございました．今回は内容を絞ったので，ちゃんと時間内に収まってよかったです．:-)
  • ないです。
    --- ありがとうございます．「ないです」でもよいので，この紙は出し続けて下さい．
  • 特になし．
    --- はい，「特になし」でもよいので，この紙は出し続けて下さい．
  • 特になし．
    --- はい，「特になし」でもよいので，この紙は出し続けて下さい．
  • スライドのグラフは何で作っていますか？
    --- 理由を問われているのではなく，方法を問われているものとします． IPEです．
  • グラフおもしろい！
    もっと色んな問題を知りたい．勉強します！
    --- ぜひ勉強して下さい :-)
  • NPに含まれる問題でもSATだったり，グラフだったり，様々な分野の問題があっておもしろいです．
    --- そうですね．それを理解することがこの講義の目標の1つです．
  • 講義の説明が理解しやすいです．
    --- ありがとうございます．質問がありましたら，いつでもどうぞ．
  • 復習用の演習や例題があると助かります。
    --- その点については，この講義を設計するときに悩みました．結論から言うと，演習を作るのはなかなか難しいです．最終的には，レポート課題が復習用の演習になります．
  • 最近、運動を始めました。既に筋肉痛が2日後に来るので、私は代謝が死んでいます。
    --- 毎日運動すれば，筋肉痛が2日前から来てるのか，1日前から来てるのか，判断できなくなるので，問題ないのでは，と思いました．;-)
  • ハミルトン閉路問題がとてもわかりやすかったです。
    --- よかったです．この証明は教科書などでも割とあっさり書いてあって，慣れていないと，理解にかなり時間をとります．授業では，かなりかみ砕いたつもりなのですが，それでも分かりにくい所があると思います．分からない所がありましたら，どしどしご質問をお願いします．
  • 無向グラフのハミルトン閉路問題において○がYes入力ならば、有向グラフのハミルトン閉路問題でも○がYes入力になりそうですかね？
    そうだとしたら
    

    ○	$\mapsto$	○
    ○ ○	$\mapsto$	○ ○
    ○─○	$\mapsto$	○ ○

    のように $|V| \leq 2$ の場合に辺を取り去る操作としてもよい気がしてきます．
    --- この指摘は完璧に正しいです．そのようにしても全く問題はありません．講義では一例を示しただけなので，他のやり方はもちろんあります．
  • ハミルトン閉路の様々な応用を知りたいと思った。
    --- ハミルトン閉路の応用として最も顕著なものは巡回セールスマン問題だと思います．巡回セールスマン問題に関する情報はThe Traveling Salesman Problemにまとめられています．また，一般的に，いろいろな問題の応用に関してはOR事典Wikiが詳しいように思いますが，例が偏っていたり，内容が古かったりするので，その点は注意が必要です．
  • 巡回セールスマン問題の例題で，辺重み和8以下のハミルトン閉路は存在しない．
    証明
    ハミルトン閉路に含まれる辺は，ちょうど5本である．重みの和が8以下になる，辺を5本選ぶ方法は唯1つ存在するが，これはハミルトン閉路ではない。□
    --- おお，その通りですね．ありがとうございます．
  • 聞いてみたら、単純なガジェットでも、考えつくのは難かしいだろうなと思いました．
    --- その通りだと思います．うまくガジェットを考えるところが研究としての主要な部分となります．
  • 僕も無向グラフ上の問題より有向グラフ上の問題の方が難しいという直感を持っていたのですが、あるあるだったようで嬉しい (？) です
    --- 嬉しさが共有できて，私も嬉しい (？) です．
  • 直感から考えると辺に対する問題でNP完全なら頂点でもNP完全だと勘がつかえそうだと思いました．
    --- 私は割と直感を大事にするので，そのような点もこの講義でお伝えできれば，と思っています．
  • 直感を命題みたいに書くの面白いですね．
    --- 直感をできる限り定式化するのは，心がけています．もしかしたら「経験則」と呼んでもよいのかもしれませんが，そこまで強く主張するほどでもないので「直感」としています．
  • 頂点に関する問題／有向グラフの問題が辺に関する問題／無向グラフの問題と同じ程度以上に難しいというのは証明されていないという点で直感なのですか。もしかしたらそうでない例が発見される可能性も残っていますか。
    --- 「証明されていない」という点で直感です．その理解で私の意図は伝わっています．
    「証明されていない」ということの意味は複数ありえます．その1つとして重要なものは，これをそもそも数学的に書き下すことができない，という点があります．講義では，独立集合問題とマッチング問題を並べて書いていますが，そもそも独立集合問題における頂点の役割を辺に置き換えたものが本当にマッチング問題なのかどうか，ということには議論の余地があります．
    質問の後半についてですが，そうでない例は実際存在します．例えば，与えられたグラフにオイラー回路がいくつあるか数えるという問題です．(つまり，これはYesかNoかを問う判定問題ではなく，「数」を問う問題です．数え上げ問題とか計数問題と呼ばれたりします．) この場合，有向グラフでは多項式時間で解けますが，無向グラフの場合NP困難 (より正確には#P完全) であることが知られています．
  • ハイパーグラフでも頂点に関する問題の難しさ ≧ 辺に関する問題の難しさ？
    --- これはちょっと微妙な要素を含んでいるのですが，「ハイパーグラフに関する問題は大抵NP完全なので，あまり変わらない」というのが，ここでの私の回答です．もう少し踏み込んだ解答は第6回の講義の内容になる予定です．
• 11/5 (4) グラフに関する問題 (1)：部分集合の選択
  • コメントをありがとうございました．
  • 3彩色問題において、3色で塗れることがどうして重要なのですか．
    入力が0, 1なのにそこにBが出てきてわからなくなりました．
    --- 様々な質問が混み入っているので，分けて答えます．
    まず，「3彩色問題」というもの自体を受け入れる必要があります．我々は3色で塗りたいのです．例えば，$n$ 人のグループを3つのクラスに分けたいけど，クラス内には互いに嫌いな人がいてはいけない，というような方法があるか？という問題は3彩色問題と見ることができます．(一人一人を頂点だと思い，互いに嫌いな人どうしを辺で結ぶことで，グラフを作ればよいです．) そうすると，3彩色問題が効率よく解けるのか，またはそうではないのか，ということを知りたくなります．(アルゴリズム的問題解決における「計画をたてる」の部分です．)
    そして，「3彩色問題はNP完全である」ということを授業では証明しました．証明では，3-SATが3彩色問題に多項式時間多対一帰着可能であることを示しました．そのために，3-SATの入力を3彩色問題の入力に変換するアルゴリズムを考えました．その際に，0, 1, Bという名前のついた頂点を使いました．これらの頂点の名前は別に0, 1, Bである必要はありません．何でもよかったのです．ただ，説明の都合上 (といっても授業ではさほど説明しませんでしたが) 0, 1, Bとしたのです．0, 1という名前の付け方が分かりにくいと思ったら，A, B, Cでも構わなかったので，そのように読み直して下さい．
  • 何も分からなかった
    --- それは困りました．とりあえず，どこから分からなくなったのか，ということは分かるでしょうか？
  • 作ったんですねぇ、グラフ．．．
    --- はい，作ったんです．;-)
  • 久しぶりに彩色問題の部品を見てなつかしく思いました
    --- この部品でなくてはならないわけではないので，それには注意して下さい．
  • 3彩色問題の例をみて3-SATを使った多対一多項式時間帰着の理解がすっきりした
    --- それはよかったです．:-)
  • 特にないです
    --- ありがとうございます．何か質問があったら，そのときにはお願いします．
  • 大変寒くなりました．教室にも寒いです
    --- そうですね．季節の変り目は体調を崩しやすいので，気をつけて下さい．
  • SATからグラフの問題に帰着させるときはグラフがごちゃごちゃしがちですね。
    --- そうですね．今回の授業ではあまり直感をお伝えできなかったと思うので，次回はもう少し直感をお伝えできるようにしてみます．
  • 3SATが3彩色問題に帰着可能であることを示す証明はとても関心しました。
    --- これでも証明としては割とシンプルな方なのです．もう少し複雑な例も今後でてきます．
  • グラフG=(V,E)
    Gの補グラフG'=(V,E')
    

    SがGの独立集合	⇔	SがG'のクリーク
    $\Updownarrow$		$\Updownarrow$
    V-SがGの頂点被覆	⇔	？

    --- 「？」の部分の名前は思いつかないです．私も知りたいです．
  • P=NP疑惑にだまされないためにも，(3彩色可能性問題などがNP完全であることを示すときに) CNF論理式から作ったグラフの頂点と辺の数がもとの節の数，リテラルの数の多項式であることを確かめるのは重要なことである．
    --- そうですね．帰着はアルゴリズムなので，それが多項式時間アルゴリズムなのかどうか，しっかりと確認して下さい．
  • 3彩色の証明は難かしかった．違う問題からの帰着の方が簡単かもしれないとかはどう考えるのか疑問におもいました．やはり数をこなしてなれるしかないのでしょうか？
    --- もしかしたら，他の問題を帰着する方が簡単かもしれません．見つけられたら，ぜひ教えてください．
  • ある問題を別の問題に帰着させるやり方は慣れればできるようになる、というのが僕にとっては不思議です．慣れるためにはどのような経験をどれくらいつむものなんでしょうか．
    --- 帰着はアルゴリズムなので，普通のアルゴリズム設計と同じ感覚を私は持っています．つまり，ある程度の訓練を積んだ人は，問題を見て，適切なアルゴリズムを思いつきます．それはアルゴリズムの設計に慣れていたり，定石を知っていたり，様々な要因をもとにしているのではないかと思います．
  • 独立集合問題を3SATに変換する方法が気になりました．
    --- 3-SATはNP完全で，独立集合問題はNPに所属するので，独立集合問題が3-SATに多項式時間多対一帰着可能であることは分かります．しかし，具体的にどのように帰着すればよいのか，ということは別の問題です．これにはいろいろな困難を伴いますが，まずCNF-SATに帰着してみます．そのためには，「SAT符号化」や「SAT定式化」，つまり，SATソルバーを使うための技法を使うことができます．その次に，CNF-SATを3-SATに帰着します．これは講義で扱ったとおりです．これをつなげることで，独立集合問題を3-SATに帰着することができます．
• 10/29 (3) 充足可能性問題とその変種
  • コメントをありがとうございました．
  • 寒くなってきてかぜをひきました
    --- お大事に．
  • なし
    --- 「なし」でもよいので，この紙は出し続けて下さい．何かあったときには，コメントをお願いします．
  • 特になし
    --- 「特になし」でもよいので，この紙は出し続けて下さい．何かあったときには，コメントをお願いします．
  • 雨が多くて嫌な気分
    --- そういう季節なので仕方ないです．あきらめましょう．
  • 今日〜がわ〜たし〜の
    バースデー (・ω・)
    --- おお，おめでとうございます！
  • :)
    --- (^-^)
  • スビードがちょと速い．理解するため時間がほしい
    --- すみません，この講義は時間配分がちょっとうまくいっていません．今回は「前回の復習」が長すぎました．できる限り改善します．
  • タコ
    イカ
    
    --- たこ足配線には気をつけて下さい．;-)
  • 論理回路の記号 (など) が一見して分かりづらいと何となく思っていたのですが、先生が同じことを感じていたことを聞いて親近感がわきました。
    --- そうなんですよ！ 本当に，どうして，あれを見てANDだと思えるのか，知りたいです．
  • すごく楽しそうに授業されていて，こちらも理解が深まりました。
    --- 楽しそうだということが伝わって，私もうれしいです :-)
  • 「N=NP解けちゃった！？」ってよくなる話好きです。どんな物でなったのか，可能な範囲で聞きたいです。
    --- 「P=NP」ですね．どんな物でなったのか，ということまで覚えていませんが，頻繁に起きていることは覚えています．しかし，これ (P=NPになってしまうから何かおかしいこと) に気付くのは重要で，この講義の内容が身につくと，そのような考察から，自分の考えていることの誤りに気付くのです．この講義の内容は皆さんの持っている問題解決の方法論を根本から変えてくれる可能性があります．ぜひ身につけて下さい．
  • ソルバーはCNF-SATをさっと解く．
    --- しかし，残念ながら，多項式時間ではないのです…
  • どうしてNo入力は扱いにくいのですか？
    --- 多項式時間多対一帰着の証明のところのことだと思います．3-CNF論理式 $f'$ がNo入力であることを証明するためには，$f'$ のすべての割当 $a'$ に対して，$f'(a')=0$ となることを証明しなくてはなりません．この「すべての割当」を考える，ということが扱いにくいのです．一方，CNF論理式 $f$ がYes入力であることを示すためには，$f$ のある割当 $a$ に対して，$f(a)=1$ となることが証明できればよいです．この場合は，「ある割当」なので，そのような割当が1つでも存在すればよいわけです．そのため，扱いやすくなると，考えています．
  • 3-SATはNP完全、この証明はすごいです．
    --- このコメントの迫力もすごかったです ;-)
  • cook levinの定理は所属研究室の輪講で取り扱ったことがあるが正直理解できなかった．
    --- この定理の証明は，非決定性Turing機械の動作を論理式で書き下す，ということを行う手法がよく知られていますね．基本的な考え方は割と単純なのですが，細かい所を詰めようとすると，確かに面倒だと思います．
  • 2CNFの例と3CNFの例が ( ) の数を示してるのか ( ) の中にある変数の数を示しているのかちょっとわかりにくいです．
    --- 確かにそうですね．修正しました．
  • CNF充足可能問題とDNF充足可能問題は見た目は似ているのに大きな違いがあることを実感しました．
    --- これは重要な視点です．私たちは問題解決をするときに，入力がどのように与えられるのか，ということに注意を払うべきなのです．案外，これは無視されています．大抵の場合，ある種の入力形式にしか対応しないようなアルゴリズム (やソフトウェア) を作成してしまい，それ以外の形式の入力に対しては，入力を変換することで対応しようとします．しかし，CNF論理式をDNF論理式に変換する例でも示した通り，その変換によって，サイズが大きく変化してしまうことがあるのです．つまり，これは，入力として使われることになるデータの収集，蓄積，そして管理にまで影響を及ぼします．皆さんもこれを教訓だと思って，今後参考にして下さい．
  • CNF論理式は3-CNF論理式に (多項式時間で) 変換できるとわかったが，2-CNF論理式に変換する方法は知られていないのですかね．
    --- CNF論理式を2-CNF論理式に多項式時間で変換する方法は知られていないと思います．実際，2-SAT (2-CNF論理式を入力とする充足可能性問題) は多項式時間で解けます．つまり，CNF論理式を2-CNFに多項式時間で変換する方法があると，CNF-SATが多項式時間で解けて，P=NPになります．3-SATはNP完全ですが，2-SATは多項式時間で解ける，という事実は割と重要です．
  • NP完全な問題もクラスNPに属するので、他のNP完全な問題に対してお互いに多項式時間多対一帰着可能ってことですよね...？ 3-SATや他の有名なNP完全な問題 (ハミルトン閉路問題) がある意味等価のように考えられるのは不思ぎです．
    --- 前半部の指摘は正しいです．今回はSATソルバーの話を少ししましたが，例えば，研究としては「ハミルトン閉路問題ソルバー」で高速なものが作れれば，NPに所属する問題はどれもハミルトン閉路問題に多項式時間で帰着されるので，その「ハミルトン閉路問題ソルバー」を用いて問題解決を行うという方法論が (原理的には) できます．これは机上の空論のように思えるかもしれませんが，これと似たことは現実になりつつあります．それは「量子アニーリング」という技術です．これは，誤解を恐れずに単純化して述べると，「最大カット問題ソルバー」で高速なもの (であると期待されているもの) です．そして，最大カット問題はNP困難問題なので，NPに所属する問題はすべて最大カット問題に多項式時間で帰着されます．つまり，量子アニーリングを使うと，NPに所属する問題が解けることになります．ただし，多項式時間で解けるわけではないようですし，解けるといっても近似的にしか解けないようです．(また，計算原理が普通のコンピュータと違うので，多項式時間で厳密に解けたとしても，P=NPになるとは限らないと思います．)
    なお，ハミルトン閉路問題については，第5回講義で扱う予定です．
• 10/15 (2) 速習 P vs NP問題
  • コメントをありがとうございました．来週は祝日でお休みですので，ご注意ください．
  • おなかがすきました．
    --- 食べて下さい ;-)
  • 遅刻は何分まで許されますか？
    --- 何分遅刻しても構いませんし，欠席しても罰則はありません．出席はとっていません．出席するかどうかは，ご自身で判断して下さい．
  • 風邪ぎみです。急に寒くなったので、先生もお気を付けください。
    --- ありがとうございます．ご自愛ください．
  • 急激な気温の変化に対応できないです．
    --- 分かります．衣替えしましょう．
  • 特になし
    --- 「特になし」でもよいので，継続してこの紙を提出するようにしていって下さい．
  • ないです。
    --- 「特になし」でもよいので，継続してこの紙を提出するようにしていって下さい．
  • 台風どうでした？
    --- 私は「避難勧告」が出たところに住んでいます．多摩川が決壊しそうだったので．かなり慎重に見守っていました．
  • 先生自身，台風の被害はありましたか？
    --- 幸いにも，被害はなかったです．
  • 日本語難しい
    --- 私もそう思います．私の講義では日本語を理解することを重視しています．私自身もできる限り理解しやすい表現を心がけていますが，うまくいかないときもあるので，その場合は，ぜひ指摘して下さい．
  • 良い授業です．多項式、合成数、素数の基本を理解した．
    --- 合成数や素数は今後出てこないかもしれません．今回は，例として出しました．
  • 「合成数」は1を含むのでしょうか？
    その名の由来は「複数の素数によって合成できる」ことだったと思うので。
    もし，1が素数でも合成数でもなかったら，今回の講義は怪しくなりそうです．
    --- ご指摘ありがとうございます．たしかに「1」の扱いがよくなかったです．講義資料を (第1回のものも含めて) 修正し，合成数判定問題の入力は2以上であることにします．
    また，1は素数でも合成数でもない，と普通はみなすようです．
  • やっぱりNP完全と困難はややこしいですね．
    --- 「NP困難」の定義は紹介しないでおこうと思ったのですが，紹介しないと，それはそれで混乱を招くと思い，紹介することにしました．この講義ではもっぱら判定問題を扱っていくので，NP完全でないNP困難問題は扱わないことになると思います．
  • 特になし．NP問題 趣味ある．
    --- 「NP問題」という言い方は，この講義でしないことにします．そのように呼ぶ流儀もあるのですが．(しかし，その流儀においても，「NP問題」と「NP完全問題」は異なる概念なので，注意して下さい．)
  • $P \in \mathrm{P}$…？？？
    --- 確かに紛らわしかったですね ;-) 問題 $P$ とクラス $\mathrm{P}$ です．書体 (フォント) が違うものは概念としても違うと認識して下さい．
  • 計算複雑性の話はあまり勉強してこなかったので この講義で勉強したいと思います．
    --- 第1回でも述べたのですが (そしてシラバスにも書いてあるのですが)，この講義は計算複雑性の講義ではありません．つまり，この講義で計算複雑性は勉強できないことになっています．その点はご注意ください．
  • 帰着のところから難しかったです。
    --- すみません．あまり具体例がなかったからだと思います．次回から具体例ばかりになるので，それで理解を補完して下さい．
  • P＝NP問題 去年は理解できなかったのですが 少し分かった気がしました．
    --- 一コマで理解するのはなかなか難しい内容です．1学期間で段々と慣れていけるようにしたいと思います．
  • ふわっと聞いたことのあるP=NPの話が軽くは理解できた．定義の言葉をちゃんと復習します．
    --- そうですね．定義を理解することが重要なので，そこに力点を置きましょう．
  • NPのくだりで，検証という言い回しをするのはどうしてですか．アルゴリズムの検証とアルゴリズムの実行は区別するべき概念ですか．
    --- この部分は分かりにくくて，すみません．まず，NPで検証しているのは「証拠の検証」です．「証拠の検証」と「アルゴリズムの検証」は違う概念なので，その点は注意して下さい．NPの文脈において，「証拠の検証」では，証拠が確かにYes入力であることの証拠であるかを検証します．検証を行うのはアルゴリズムです．つまり，検証するアルゴリズムを作ることになります．
    「アルゴリズムの検証」というと，それは「プログラム検証」という言い方の「プログラム」の部分を「アルゴリズム」に変えたもの，と捉えるのが普通かと思います．「プログラム検証」というと，それは作成されたプログラムが正しいプログラムであるか (例えばバグがないか) ということを検証する，というような意味で使われます．それになぞらえれば，「アルゴリズムの検証」とは，作成されたアルゴリズムが正しいアルゴリズムであるかということを検証する，という意味になると思います．
    一方，「アルゴリズムの実行」は，アルゴリズムにおけるステップを並べたもののことを指すと思います．
  • P，NP以外に知っておくべき問題のクラスはありますか．
    --- これは研究分野や興味のある分野によってだいぶ変わってきます．例えば，論理学やプログラミング言語理論だと，PやNPよりも難しい問題のクラスを考えることが多くて，例えば，PSPACEとかEXPTIMEとか，計算可能な問題のクラス (よくRと呼ばれるクラス)，とか，そういうのが出てきます．暗号理論だと，確率分布とか一方向性とかそういうものに関わる問題のクラスがよく出てきます．最適化では，近似可能性に関連する問題のクラスがあったりします．物理学では量子効果に関わる問題のクラスがよく出てきます．
    Complexity Zooというwebサイトがあります．ここには多くの問題クラスが挙げられていて，眺めるだけでも楽しい気分になります．:-)
  • non-deterministicな計算機なんて作れてないし、作れそうにもないのにどうしてこのモデルを使って計算量の議論をすることがこんなにもメジャーになったのでしょうか．
    --- いい質問です．← 言ってみたくなりました :-)
    これは次回 (第3回) の内容とも重なってきますが，まず多くの現実問題がクラスNPに所属するか，クラスNPに所属する問題に多項式時間帰着可能である，という事実があります．これを発見したのはRichard Karpであると言われています．Karpの発見以降，PとNPの違いを考えることで，問題の難しさ (つまり，達成できる実行時間の限界) に関する議論が深まることが分かったわけです．
    もう一つ重要なことがあります．それは，決定的 (deterministic) な計算と非決定的 (non-deterministic) な計算の間に差がないクラスというのは，実をいうと少なからず存在する，ということです．例えば，決定性有限オートマトンと非決定性オートマトンが受理できる言語の集合は一致します (どちらも「正規言語」として特徴づけられます)．その他にも，メモリ使用量について，PSPACE = NPSPACEという等式が知られています (Savitchの定理) ．
    このように，決定性と非決定性が一致するような状況では，「非決定性を用いてアルゴリズムの設計を行い，それを決定的アルゴリズムに変換する」というアルゴリズム設計技法が使えるようになります．これは実際に有限オートマトンではよく行われることで，つまり，「非決定性の柔軟さを活かして有限オートマトンを設計し，実装する場合には，それを決定性有限オートマトンに変換したものを考える」という考え方ができるわけです．
    現実世界で作ることができない「計算」というものを考えられる，というのが抽象論，すなわち，数学の強力なところです．「多項式時間で解ける問題」がどういうものか考えるためには，「多項式時間で解けない問題」がどういうものか考える必要もあるわけです．そのギリギリの狭間にP vs NP問題は挑戦しているのだと思います．
  • NP完全問題を多項式時間で解くような「神がかり的」なアルゴリズムがあると思います。
    --- その場合，P＝NPとなりますね．おそらく，現状の大問題は，われわれ人類が，それほど多くのアルゴリズム設計技法を持っていない，ということです．われわれ人類が，いま，コンピュータの潜在能力を本当に活かしきれているのか，と問われると，私はよく分からないです．
  • P＝NPかどうかの質問で、なんとなく「分からない」という立場が多そうに思っていたが、そうではなかったのが意外に感じました．
    --- 2019年版のアンケートには続きがあって，P vs NP問題を真剣に考えたことがある人に限ると，P≠NPだと思う割合は99％に増えるそうです．どのようにして「真剣に考えたことがある」と判断しているのか不明ですが，割合としては，P≠NPを信じている人の方が多いというのは確かである気がします．
  • 先生は P≠NP のアンケートに何と答えますか？
    --- 許されるなら「分からない」と答えたいと思います．私見ですが，現状では，多項式時間アルゴリズムを設計する方法論 (理論) も，問題の複雑性を解析する方法論 (理論) のどちらも，成熟しているとは言えないと思います．計算に関する理論は，本当に本当に未成熟で，分かっていることの方が少ないぐらいだと思います．
• 10/8 (1) アルゴリズム的問題解決と計算複雑性
  • コメントをありがとうございました．以下のように掲載されます．
  • 後期、よろしくお願いします。
    --- こちらこそ，よろしくお願いします．
  • 夏休み中の生活サイクルから抜けだせないです．
    --- 生活サイクルがあったのなら，よい方だと思います．;-)
  • 履修検討してます。よろしくお願いします。
    --- こちらこそ，よろしくお願いします．
  • よろしくお願いします
    --- こちらこそ，よろしくお願いします．
  • 好きな食べものはなんですか
    --- さて何でしょう．次の5つのヒントからお答え下さい．
  • 退室が0分から5分に増えてる
    --- 退室には時間がかかります ;-)
  • 3分休憩は5分になっていかがですか
    --- とりあえず3分にします．
  • 特になし
    --- 「特になし」でもよいので，継続してこの紙を提出するようにしていって下さい．
  • 評価レポートについて
    授業の内容の理解度を確かめるような内容ですか？それとも、調べてその内容をまとめるような内容ですか？
    --- 第1回は前者，第2回は後者のような内容を考えていますが，詳細は要項説明の際に行います．
  • 『いかにして問題を解くか』を持っているのですが、読めていませんでした．今日の話を聞いて早めに読んでみようと思いました．
    --- お薦めします．ぜひ読んでみて下さい．
  • 「How to Solve It」を読んでみようと思うのですが，この本 (もしくは洋書全般) を読む時にオススメの読み方はありますか？ (まずは全体をざっくりよむ，etc)
    --- 洋書であるからといって，特別に気をつけることはないと思います．和書と同じように読めばよいと思います．
  • 「いかにして問題を解くか」は高校の図書館 (図書室) にもありました。読んだ覚えは，ないですが。
    --- 電気通信大学附属図書館にも蔵書としてあるようです．
  • プログラムで実装できないアルゴリズムが存在することに驚きました。
    --- これは「アルゴリズム」というものが抽象的であるから起こることです．そのためには「計算モデル」というものを真面目に考える必要がありますが，この講義ではそこに深入りすることはありません．
    それで終えるのも教育的ではないので，例を述べてみます．1990年代の終わり頃から，「量子アルゴリズム」というものの研究が盛んに行われるようになりました．しかし，当時は量子コンピュータと呼べるものは存在しませんでした．つまり，「アルゴリズムはあるけど，実装できない」という状況が起きていたわけです．それでは，量子コンピュータが存在しないのに，なぜ量子アルゴリズムの研究ができたのか，疑問に思われるかもしれません．それに対する答えは，量子アルゴリズムが抽象的であることに由来します．つまり，量子計算を行う計算モデル (例えば，量子回路や量子チューリング機械) を抽象的に考えて，その上で動く手続きを与えることで量子アルゴリズムは設計されるのです．これにより，量子コンピュータがなくても，量子アルゴリズムの研究ができるわけです．
  • アルゴリズムが速いことがプログラムが速いことに必ずしもつながるわけではないというのが驚きだった．
    --- これはよく勘違いされます．ご注意ください．
  • instanceの入力読み込み時間よりも少ない実行時間で終わるアルゴリズムの例はありますか？
    --- 短い答えは「あります」になります．しかし，そのようなアルゴリズムはinstanceのすべてを読むことができないので，間違った出力を行うことがあります． これは私も参加している研究プロジェクトのテーマでもあります．
  • Kruskal法がアルゴリズムの教科書で人気なのは正統性の証明が割とシンプルだからではないかと思った．
    --- これについて，私は疑問を持っています．アルゴリズムを教える多くの人が，なぜKruskal法を教えるのか，ということについて，明確な視点を持っていない気がします．
    Kruskal法は，貪欲アルゴリズムの典型例として紹介されることが多いのですが，典型例とする割には，難しいです．Kruskal法を紹介するなら，スケジューリングにはもっと分かりやすく，単純で，実装もしやすいものがいくつかあり (例えば，Smithルールと呼ばれるもの)，そのようなアルゴリズムの方が貪欲アルゴリズムの紹介としては適していると思います．グラフアルゴリズムとしても，それほど典型的なものではありませんし，使うデータ構造 (union-find) も他の場面で多用されるものではありません．
    ここで，この私の考えは，「Kruskal法が重要ではない」ということを意図しているものではありません．アルゴリズムの教育上，貪欲アルゴリズムやグラフアルゴリズムの典型例として紹介すべきものかどうか，という観点で，述べているものだということをご理解下さい．
    なお，「正統性」ではなく「正当性」なのでご注意を．
  • 
    --- 真ん中は結界でしょうか．
  • 下界と上界の説明がわかりやすかったです。
    --- それはよかったです．重要な概念なので，しっかりと身につけて下さい．
  • 上界，下界の理解が深まった
    --- 次回も出てきますので，復習をしておいて下さい．
  • 復習になってよかった
    --- 何度も繰り返すことで慣れていきましょう．
  • 常に $O(f(n)) \geq \Omega(f(n))$ ？
    --- 問われていることを私が理解できているかどうか分かりませんが，関数として， $g(n)=O(f(n))$ と $h(n) = \Omega(f(n))$ を満たす $g, h$ に対して，$g(n) \geq h(n)$ が成り立つか，という問いであると想定します．
    その問いに対して，答えは「No」です．例えば，$f(n) = n^2$, $g(n) = n$, $h(n)=n^3$ とすると，$g(n)=O(f(n))$ と $h(n) = \Omega(f(n))$ は成り立ちますが，$g(n) \geq h(n)$ は成り立ちません．

• 2回のレポートにより成績評価を行います．
• 第1回レポート
  • レポート課題：12月3日(火) 出題
    • 12月3日：問1-2を修正
  • 提出締切：12月25日(水) 23:59 JST
• 第2回レポート
  • レポート課題：1月28日(火) 出題
  • 提出締切：2月12日(水) 23:59 JST

• こちらをご覧ください

• 10/1 休み (大学院入学式)
• 10/8 (1) アルゴリズム的問題解決と計算複雑性
• 10/15 (2) 速習 P vs NP問題
• 10/22 休み (即位礼)
• 10/29 (3) 充足可能性問題とその変種
• 11/5 (4) グラフに関する問題 (1)：部分集合の選択
• 11/12 (5) グラフに関する問題 (2)：経路の選択
• 11/19 (6) 集合族に関する問題 (1)：グラフとの関連
• 11/26 (7) 集合族に関する問題 (2)：発展
• 12/3 (8) 数値が関わる問題 (1)：2分割問題
• 12/10 (9) 数値が関わる問題 (2)：3分割問題
• 12/17 (10) 平面性が関わる問題
• 12/24 冬期休業
• 12/31 冬期休業
• 1/7 (11) 計算幾何学に関する問題
• 1/14 (12) 文字列に関する問題
• 1/21 (13) アルゴリズム的問題解決：再考
• 1/28 予備
• 2/4 休講
• 2/11 休み (建国記念の日)

• Complexity Zoo
• List of NP-complete problems (Wikipedia)
• NP-intermediate (Wikipedia)

• M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979.
• B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018.
• M. Sipser, Introduction to Theory of Computation, 3rd Edition, Cengage Learning, 2012.

• 離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
• 離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
• 離散最適化基礎論 (2016年度) テーマ：グラフの木分解
• 離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム