計算複雑性理論において、計算複雑性クラスFLは、決定性チューリングマシンが対数量のメモリ空間で解くことができる関数問題の集合である。[ 1 ] Lの定義と同様に、マシンは読み取り専用テープから入力を読み取り、書き込み専用テープに出力を書き込みます。対数空間の制限は、読み取り/書き込み作業テープにのみ適用されます。
大まかに言えば、関数問題とは複雑な入力を受け取り、（おそらく同程度に）複雑な出力を生成する問題です。関数問題は、YesかNoの回答のみを出力する決定問題とは区別されます。このように、FLは決定論的対数空間で解ける 決定問題の集合Lとは区別されます。FLは、決定論的多項式時間で解ける関数問題の集合FPの部分集合です。[ 1 ]
FLには、数に関する算術を含むいくつかの自然問題が含まれていることが知られています。対数空間を用いた2つの数の加減乗算は比較的単純ですが、除算ははるかに奥深い問題であり、数十年にわたって未解決でした。[ 2 ] [ 3 ]
同様にFNLを定義することもできるが、これはFNPとNPの関係と同じ関係をNLと持つ。[ 1 ]
参考文献
- ^ a b cアルバレス、カルメ;バルカサル、ホセ L. Jenner、Birgit (1991)、「並列時間の尺度としての関数型オラクル クエリ」、STACS 91、Lecture Notes in Computer Science、vol. 480、Springer、pp. 422–433、doi : 10.1007/BFb0020817、hdl : 2117/327984、ISBN 3-540-53709-0。
- ^ Chiu, A.; Davida, G.; Litow, B. (2001)、「対数空間一様NC1における除算」、RAIRO理論情報学および応用、35 (3): 259– 276、doi : 10.1051/ita:2001119。
- ^ Allender, Eric (2004)、「部門のブレークスルー」(PDF)、理論計算機科学の最新動向、World Scientific、pp. 147– 164。
