DTIME による複雑性クラス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 02:26 UTC 版)
「DTIME」の記事における「DTIME による複雑性クラス」の解説
多くの重要な複雑性クラスが DTIME を使って定義される。それらのクラスは決定性時間のある量を使って解ける問題を含むものである。任意の時間構成可能関数を使って複雑性クラスを定義できるが、研究に値するクラスは限られている。一般に、複雑性クラスは計算モデルを変更しても安定していることが望ましく、サブルーチンの合成について閉じているのが望ましい。 DTIME は時間階層定理に従う。すなわち、漸近的に多くの時間を指定すると、常により大きな問題の集合が生成される。 よく知られている複雑性クラス P は、多項式量の DTIME で解ける問題のクラスである。形式的には以下のように定義される。 P = ⋃ k ∈ N DTIME ( n k ) {\displaystyle {\text{P}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}\left(n^{k}\right)} P は線形時間問題 DTIME ( n ) {\displaystyle {\text{DTIME}}(n)} を含む最小の安定したクラスである (AMS 2004, Lecture 2.2, pg. 20)。また、Pは「現実的計算可能」な最大の複雑性クラスの一つと考えられている。 決定性時間を使うより大きなクラスとして EXPTIME がある。EXPTIME は決定性機械で指数関数時間を使って解ける問題のクラスである。形式的に示せば、以下のようになる。 EXPTIME = ⋃ k ∈ N DTIME ( 2 n k ) . {\displaystyle {\text{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\text{ DTIME }}\left(2^{n^{k}}\right).} より大きな複雑性クラスも同様に定義できる。時間階層定理により、これらのクラスは厳密な階層を形成する。例えば P ⊊ EXPTIME {\displaystyle {\text{P}}\subsetneq {\text{EXPTIME}}} などとなる。
※この「DTIME による複雑性クラス」の解説は、「DTIME」の解説の一部です。
「DTIME による複雑性クラス」を含む「DTIME」の記事については、「DTIME」の概要を参照ください。
- DTIME による複雑性クラスのページへのリンク
