計算問題を「決定問題」という形式に変換することで、異なる問題の難しさを公平に比較できるようになることを理解する。複雑性理論の共通言語として決定問題が選ばれた理由を把握し、最適化・探索・計数などの問題を決定問題に変換するテクニックを身につける。

最適化問題（最短路を求めよ）や探索問題（条件を満たす解を見つけよ）は形が様々で、そのまま比較すると難しさの基準がずれてしまう。Yes/No の二値に統一することで、あらゆる計算問題を同じ目盛りで測ることができる。理論の整合性を保ちながら、最終的には最適化版への応用もできる汎用的な枠組みになる。

決定問題とは、入力 x に対して「Yes」か「No」の二値で答える問題のこと。形式的には文字列の集合（言語）L ⊆ {0,1}* として表現し、「x は L に属するか？」を判定する問題と同一視する。計算機は入力 x を受け取り、x ∈ L なら受理（Yes）、x ∉ L なら拒否（No）して停止する。

最適化問題をいきなり解こうとすると比較が難しい。しかし「長さ k 以下の解が存在するか？」という Yes/No 問いに変えると、アルゴリズムの挙動を単純なフラグで評価できる。k を変化させながら二分探索すれば最適値も求まるので、決定版を制した瞬間に最適化版も制したも同然になることが多い。難しさを一点に凝縮する操作が決定問題化の本質。

グラフ G と整数 k が与えられたとき、「G に長さ k 以下のハミルトン路が存在するか？」という問いは決定問題。一方「最短のハミルトン路を求めよ」は最適化問題で決定問題ではない。前者で Yes/No が言えれば、k を二分探索することで後者の最小長も求まる。

「決定問題しか扱わないなら、最適化や探索は無視しているのでは？」という疑問はよくある。実際には逆で、まず決定版として難しさを証明し、その結果を最適化版・計数版に応用する手順を踏む。決定問題への変換は制限ではなく、理論構築のための出発点。また「Yes/No しかないので表現力が弱い」という誤解もあるが、驚くほど多様な問題がこの形式で表せる。