非基本的な問題

計算複雑性理論において、 非基本問題^[1]はELEMENTARYクラスに属しない問題である。クラスとしてはNONELEMENTARYと表記されることもある。

非基本的な問題であるが決定可能な問題の例には次のものがあります。

補完を伴う正規表現の等価性の問題^[2]
木上のモナド二階論理の決定問題（S2S参照）^[3]
項代数の決定問題^[4]
WVOクワインの一階述語論理の溝付き断片の充足可能性^[5]
型付きラムダ計算における2つの閉じた項のβ変換可能性の決定^[6]
ベクトル加算システムにおける到達可能性。アッカーマン完全である。^[7]^[8]
ペトリネットにおける到達可能性。アッカーマン完全である。^[9]^[8]

参考文献

^ Vorobyov, Sergei; Voronkov, Andrei (1998)、「複雑な値を持つ非再帰的論理プログラムの複雑さ」、Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98)、ニューヨーク、ニューヨーク、米国: ACM、pp. 244–253、CiteSeerX 10.1.1.39.8822、doi :10.1145/275487.275515、ISBN 978-0-89791-996-8、S2CID 15631793。
^ Stockmeyer, Larry J. (1974)、「オートマトン理論と論理における決定問題の複雑性」(PDF)、マサチューセッツ工科大学博士論文
^ Libkin, Leonid (2006)、「ランク付けされていないツリーのロジック: 概要」、Logical Methods in Computer Science、2 (3): 3:2、31、arXiv : cs.LO/0606062、doi :10.2168/LMCS-2(3:2)2006、MR 2295773。
^ Vorobyov, Sergei (1996)、「木の基本理論の改良された下限値」、Automated Deduction — CADE-13: 13th International Conference on Automated Deduction、ニューブランズウィック、ニュージャージー、米国、1996 年 7 月 30 日～8 月 3 日、議事録、Lecture Notes in Computer Science、vol. 1104、Springer、pp. 275～287、CiteSeerX 10.1.1.39.1499、doi :10.1007/3-540-61511-3_91、ISBN 978-3-540-61511-8。
^ イアン、プラット＝ハートマン;シュヴァスト、ヴィースワフ。 Tendera、Lidia (2016)、「Quine のフルートの断片は初歩的ではない」、Talbot、Jean-Marc に掲載。 Regnier、Laurent (編)、第 25 回コンピューターサイエンスロジックに関する EACSL 年次会議、CSL 2016、2016 年 8 月 29 日から 9 月 1 日まで、フランス、マルセイユ、LIPIcs、vol. 62、Schloss Dagstuhl - Leibniz-Zentrum für Informatik、pp. 39:1–39:21、doi : 10.4230/LIPIcs.CSL.2016.39
^ スタットマン、リチャード（1979）、「型付きλ計算は初等再帰的ではない」、理論計算機科学、9：73-81、doi：10.1016/0304-3975（79）90007-0、hdl：2027.42/23535。
^ Czerwiński, Wojciech; Orlikowski, Łukasz (2021).ベクトル加算システムの到達可能性はアッカーマン完全である. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). arXiv : 2104.13866 .
^ ab Brubaker, Ben (2023年12月4日). 「簡単に聞こえる問題が、私たちの宇宙には大きすぎる数字を生み出す」. Quanta Magazine .
^ Leroux, Jerome (2022年2月). 「ペトリネットの到達可能性問題は原始再帰的ではない」. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. pp. 1241–1252. arXiv : 2104.12695 . doi :10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6。

[1] Vorobyov, Sergei; Voronkov, Andrei (1998)、「複雑な値を持つ非再帰的論理プログラムの複雑さ」、Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98)、ニューヨーク、ニューヨーク、米国: ACM、pp. 244–253、CiteSeerX 10.1.1.39.8822、doi :10.1145/275487.275515、ISBN 978-0-89791-996-8、S2CID 15631793。

[2] Stockmeyer, Larry J. (1974)、「オートマトン理論と論理における決定問題の複雑性」(PDF)、マサチューセッツ工科大学博士論文

[3] Libkin, Leonid (2006)、「ランク付けされていないツリーのロジック: 概要」、Logical Methods in Computer Science、2 (3): 3:2、31、arXiv : cs.LO/0606062、doi :10.2168/LMCS-2(3:2)2006、MR 2295773。

[4] Vorobyov, Sergei (1996)、「木の基本理論の改良された下限値」、Automated Deduction — CADE-13: 13th International Conference on Automated Deduction、ニューブランズウィック、ニュージャージー、米国、1996 年 7 月 30 日～8 月 3 日、議事録、Lecture Notes in Computer Science、vol. 1104、Springer、pp. 275～287、CiteSeerX 10.1.1.39.1499、doi :10.1007/3-540-61511-3_91、ISBN 978-3-540-61511-8。

[5] イアン、プラット＝ハートマン;シュヴァスト、ヴィースワフ。 Tendera、Lidia (2016)、「Quine のフルートの断片は初歩的ではない」、Talbot、Jean-Marc に掲載。 Regnier、Laurent (編)、第 25 回コンピューターサイエンスロジックに関する EACSL 年次会議、CSL 2016、2016 年 8 月 29 日から 9 月 1 日まで、フランス、マルセイユ、LIPIcs、vol. 62、Schloss Dagstuhl - Leibniz-Zentrum für Informatik、pp. 39:1–39:21、doi : 10.4230/LIPIcs.CSL.2016.39

[6] スタットマン、リチャード（1979）、「型付きλ計算は初等再帰的ではない」、理論計算機科学、9：73-81、doi：10.1016/0304-3975（79）90007-0、hdl：2027.42/23535。

[7] Czerwiński, Wojciech; Orlikowski, Łukasz (2021).ベクトル加算システムの到達可能性はアッカーマン完全である. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). arXiv : 2104.13866 .

[:0-8] Brubaker, Ben (2023年12月4日). 「簡単に聞こえる問題が、私たちの宇宙には大きすぎる数字を生み出す」. Quanta Magazine .

[9] Leroux, Jerome (2022年2月). 「ペトリネットの到達可能性問題は原始再帰的ではない」. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. pp. 1241–1252. arXiv : 2104.12695 . doi :10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6。