ログCFL

計算複雑性理論において、LOGCFLは対数空間で文脈自由言語に還元できるすべての決定問題を含む計算複雑性クラスである。^[1]このクラスは相補性の下で閉じている。^[1]これはNLとAC ¹の間に位置し、前者^[1]を含み後者に含まれるという意味である。 ^{[2] LOGCFLにとって}完全な問題には、非巡回ハイパーグラフで特徴付けられる多くの問題が含まれる。

参照

^ abc Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002)、複雑性理論コンパニオン、理論計算機科学テキスト: EATCS シリーズ、Springer、p. 280、doi :10.1007/978-3-662-04880-1、ISBN 9783662048801
^ カプロン、ブルース・M.編（2023年）、ロジック、オートマトン、計算複雑性：スティーブン・A・クックの著作、ACMブックス、モーガン＆クレイプール、p. 124、ISBN 9798400707803
^ ab Gottlob, Georg; Leone, Nicola; Scarcello, Francesco (2001)、「非巡回結合クエリの複雑さ」、Journal of the ACM、48 (3): 431–498、doi :10.1145/382780.382783
^ Vortmeier, Nils; Kokkinis, Ioannis (2021)、「非巡回ハイパーグラフ準同型の動的複雑性」、Kowalik, Lukasz; Pilipczuk, Michal; Rzazewski, Pawel (編)、Graph-Theoretic Concepts in Computer Science - 47th International Workshop、WG 2021、ワルシャワ、ポーランド、2021 年 6 月 23 ～ 25 日、改訂選択論文、Lecture Notes in Computer Science、vol. 12911、Springer、pp. 232 ～ 244、arXiv : 2107.06121、doi :10.1007/978-3-030-86838-3_18、ISBN 978-3-030-86837-6