2026年07月21日 第#number#回
今回の授業を通じて、 計算量のオーダーを比較する際の「支配」という考え方の実践的な計算方法と、 P・NP・NP完全・NP困難という計算複雑性理論の基本的な分類体系を一通り理解できた。 「NP＝多項式時間で解けない」という誤解を明確に否定してもらえたことで、 この分野の考え方の背景にある「証明されていないことを断定しない」という姿勢が印象に残った
理解できましたか．
今回はビッグOの定義と、
支配・支配項の話でした。
前回途中で終わっていた「Cと十分大きなNが存在してf(n)≤C・g(n)」ってやつ、
ちゃんと定義として整理してもらえたので、
やっと腹落ちした感じがします。
支配のところは、
基本関数のリスト(対数→多項式→多項式×指数→二重指数)の後ろにあるものほど前を支配するという仕組みで、
logn³とlognとかn²とnlognとか、
例をいくつも解いているうちに、
だんだん感覚でわかるようになってきました。
あと個人的に一番「気をつけなきゃ」と思ったのが、
n²・n⁴・n⁵みたいに次数が同じものは先にまとめてから比較する、
というところです。
普通にやると見落としそうなので覚えておきたいです。
dt(fg)=dt(f)・dt(g)とか、
logを取ると指数と多項式の差が消えてしまう話も、
普通に面白かったです。
計算量については問題はなさそうですね．
今日の講義で印象に残ったのは,Class PとClass NPの名称の由来です.Pは"Polynomial time solvable",NPは"Non-deterministic Polynomial time"に由来していて,あえて"deterministic"という言葉が用いられている背景が興味深かったです.通常であれば「Not P」と定義したくなるところ,NP完全問題を多項式時間で解くアルゴリズムが将来発見される可能性を排除していないため,現在のような名称になっていることが印象的でした.
そうですね．理解できているようで，よろしいと思います．
今回の授業では、 まずビッグオー記法を使って、 関数の増加の速さやアルゴリズムの計算量を表す方法を学んだ。 多項式関数や指数関数では、 入力サイズが大きくなるほど実行時間に大きな差が生まれることが分かった。 また、 Pは多項式時間で解ける問題、 NPは答えが正しいかを多項式時間で確認できる問題であり、 PはNPに含まれることを理解した。 さらに、 多項式時間帰着、 NP困難、 NP完全についても学び、 NP完全問題を一つでも多項式時間で解ければP＝NPになるという点が特に印象に残った。 PとNPが等しいかどうかは現在も未解決であり、 計算量の考え方が問題の難しさを判断するうえで重要だと感じた。
はい大切です．色々と考えてみて下さい．
今日の講義と演習課題を通して、 計算爆発の恐ろしさと計算量クラスの概念についてしっかり理解することができました。 ハノイの塔や巡回セールスマン問題の計算量を実際に見積もってみて、 対象の数が増えるとコンピュータがいくら高速でもしらみつぶしの探索では現実的な時間で解けなくなることが数式から実感できました。 また、 クラスNPがNot Polynomialの略ではなく非決定性チューリング機械で多項式時間で解けるという意味であることや、 P対NP問題の全体像も自分の中で整理できました。 疑問に思った点としては、 巡回セールスマン問題で厳密な答えを出すのが現実的に不可能であるならば、 実際の配送などの現場ではどうやって実用的な計算時間に収めているのかが気になりました。 それから、 非決定性チューリング機械というモデルの振る舞いがまだ少し抽象的でイメージしきれていない部分があるので、 今後の授業を通してさらに理解を深めていきたいです。
実際の現場では，発見的な方法というか，これまでの経験的なところで， 配送順を考えているのではないでしょうか．
NPをnot polynomialにしたいが、 できないという点が興味深かった。 数学などでは、 問題を解くことの証明は容易だが、 解けないことを示すことはとても難しいと感じた。 また、 ビックオー記法について、 求め方は習っていたが、 定義などを知ることができてよかった。
理解できたようですね．