決定問題と言語

アルファベットを $\Sigma = \{0, 1\}$ とし、$\Sigma^{*}$ で有限長のビット列全体を表します。$\Sigma^{*}$ の部分集合 $L$ を言語と呼びます。決定問題とは、入力 $x \in \Sigma^{*}$ に対して「$x \in L$ か」を答える問題のことであり、決定問題と言語を同一視します。数学的対象 $O$（グラフ、論理式、整数の列など）をビット列に符号化したものを $\langle O \rangle$ と書きます。入力サイズ $n$ とは、入力ビット列の長さ $|x|$ のことです。