Problema no elemental

En la teoría de la complejidad computacional , un problema no elemental ^[1] es un problema que no es miembro de la clase ELEMENTARY . Como clase, a veces se lo denomina NO ELEMENTARY.

Algunos ejemplos de problemas no elementales que, sin embargo, son decidibles incluyen:

• El problema de la equivalencia de expresiones regulares con complementación ^[2]
• El problema de decisión para la lógica monádica de segundo orden sobre árboles (ver S2S ) ^[3]
• El problema de decisión para las álgebras de términos ^[4]
• Satisfacibilidad del fragmento estriado de lógica de primer orden de WVO Quine ^[5]
• Decidir la β-convertibilidad de dos términos cerrados en el cálculo lambda tipificado ^[6]
• alcanzabilidad en sistemas de adición vectorial ; es Ackermann -completo. ^{[7] [8]}
• alcanzabilidad en redes de Petri ; es Ackermann -completo. ^{[9] [8]}

Referencias

1. Vorobyov, Sergei; Voronkov, Andrei (1998), "Complejidad de programas lógicos no recursivos con valores complejos", Actas del decimoséptimo simposio ACM SIGACT-SIGMOD-SIGART sobre principios de sistemas de bases de datos (PODS '98) , Nueva York, NY, EE. UU.: ACM, págs. 244-253, CiteSeerX  10.1.1.39.8822 , doi :10.1145/275487.275515, ISBN 978-0-89791-996-8, Número de identificación del sujeto  15631793.
2. Stockmeyer, Larry J. (1974), La complejidad de los problemas de decisión en la teoría y la lógica de los autómatas (PDF) , tesis doctoral, Instituto Tecnológico de Massachusetts
3. Libkin, Leonid (2006), "Lógica para árboles no clasificados: una descripción general", Métodos lógicos en informática , 2 (3): 3:2, 31, arXiv : cs.LO/0606062 , doi :10.2168/LMCS-2(3:2)2006, MR  2295773.
4. Vorobyov, Sergei (1996), "Un límite inferior mejorado para las teorías elementales de árboles", Deducción automática — CADE-13: 13.ª Conferencia internacional sobre deducción automática, New Brunswick, NJ, EE. UU., 30 de julio – 3 de agosto de 1996, Actas , Lecture Notes in Computer Science, vol. 1104, Springer, págs. 275–287, CiteSeerX 10.1.1.39.1499 , doi :10.1007/3-540-61511-3_91, ISBN  978-3-540-61511-8.
5. Pratt-Hartmann, Ian; Szwast, Wieslaw; Tendera, Lidia (2016), "El fragmento acanalado de Quine no es elemental", en Talbot, Jean-Marc; Regnier, Laurent (eds.), 25.ª Conferencia anual de la EACSL sobre lógica informática, CSL 2016, 29 de agosto - 1 de septiembre de 2016, Marsella, Francia , LIPIcs, vol. 62, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs. 39:1–39:21, doi : 10.4230/LIPIcs.CSL.2016.39
6. Statman, Richard (1979), "El cálculo λ tipado no es recursivo elemental", Theoretical Computer Science , 9 : 73–81, doi :10.1016/0304-3975(79)90007-0, hdl : 2027.42/23535.
7. Czerwiński, Wojciech; Orlikowski, Łukasz (2021). La accesibilidad en sistemas de adición vectorial es completa en términos de Ackermann . 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). arXiv : 2104.13866 .
8. Brubaker, Ben (4 de diciembre de 2023). "Un problema que parece fácil produce números demasiado grandes para nuestro universo". Revista Quanta .
9. Leroux, Jerome (febrero de 2022). "El problema de accesibilidad de las redes de Petri no es recursivo primitivo". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. págs. 1241–1252. arXiv : 2104.12695 . doi :10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6.