Teoría existencial de los reales

Fórmulas cuantificadas con variables de números reales.

En lógica matemática , teoría de la complejidad computacional e informática , la teoría existencial de los reales es el conjunto de todas las oraciones verdaderas de la forma

$${\displaystyle \exists X_{1}\cdots \exists X_{n}\,F(X_{1},\dots ,X_{n}),}$$

de números realesfórmula sin cuantificadorespolinomios^[1] ${\displaystyle X_{i}}$ ${\displaystyle F(X_{1},\dots X_{n})}$ ${\displaystyle F}$

El problema de decisión para la teoría existencial de los reales es el problema de encontrar un algoritmo que decida, para cada oración, si es verdadera o falsa. De manera equivalente, es el problema de probar si un conjunto semialgebraico dado no está vacío. ^[1] Este problema de decisión es NP-difícil y se encuentra en PSPACE , ^[2] dándole una complejidad significativamente menor que el procedimiento de eliminación de cuantificadores de Alfred Tarski para decidir enunciados en la teoría de los reales de primer orden sin la restricción a cuantificadores existenciales. ^[1] Sin embargo, en la práctica, los métodos generales de la teoría de primer orden siguen siendo la opción preferida para resolver estos problemas. ^[3]

La clase de complejidad se ha definido para describir la clase de problemas computacionales que pueden traducirse en oraciones equivalentes de esta forma. En la teoría de la complejidad estructural , se encuentra entre NP y PSPACE. Muchos problemas naturales en la teoría de grafos geométricos , especialmente los problemas de reconocer gráficos de intersección geométrica y enderezar los bordes de los dibujos de gráficos con cruces , pertenecen a y están completos para esta clase. Aquí, completitud significa que existe una traducción en la dirección inversa, de una oración arbitraria sobre los reales a una instancia equivalente del problema dado. ^[4] ${\displaystyle \exists \mathbb {R} }$ ${\displaystyle \exists \mathbb {R} }$

Fondo

En lógica matemática , una teoría es un lenguaje formal que consta de un conjunto de oraciones escritas utilizando un conjunto fijo de símbolos. La teoría de primer orden de campos cerrados reales tiene los siguientes símbolos: ^[5]

• las constantes 0 y 1,
• una colección contable de variables , ${\displaystyle X_{i}}$
• las operaciones de suma, resta, multiplicación y (opcionalmente) división,
• símbolos <, ≤, =, ≥, > y ≠ para comparaciones de valores reales,
• los conectivos lógicos ∧, ∨, ¬ y ⇔,
• paréntesis, y
• el cuantificador universal ∀ y el cuantificador existencial ∃

Una secuencia de estos símbolos forma una oración que pertenece a la teoría de los reales de primer orden si está gramaticalmente bien formada, todas sus variables están adecuadamente cuantificadas y (cuando se interpreta como un enunciado matemático sobre los números reales ) es verdadera. declaración. Como demostró Tarski, esta teoría puede describirse mediante un esquema axiomático y un procedimiento de decisión que sea completo y eficaz: para cada oración gramatical y completamente cuantificada, la oración o su negación (pero no ambas) pueden derivarse de los axiomas. La misma teoría describe todo campo real cerrado , no sólo los números reales. ^[6] Sin embargo, existen otros sistemas numéricos que no se describen con precisión mediante estos axiomas; En particular, la teoría definida de la misma manera para números enteros en lugar de números reales es indecidible , incluso para oraciones existenciales ( ecuaciones diofánticas ) según el teorema de Matiyasevich . ^{[5] [7]}

La teoría existencial de los reales es el fragmento de la teoría de primer orden que consta de oraciones en las que todos los cuantificadores son existenciales y aparecen antes que cualquiera de los demás símbolos. Es decir, es el conjunto de todas las oraciones verdaderas de la forma.

$${\displaystyle \exists X_{1}\cdots \exists X_{n}\,F(X_{1},\dots ,X_{n}),}$$

fórmula sin cuantificadorespolinomios realesproblema de decisiónconjunto semialgebraico^[1] ${\displaystyle F(X_{1},\dots X_{n})}$ ${\displaystyle n}$ ${\displaystyle (X_{1},\dots X_{n})}$ ${\displaystyle F(X_{1},\dots X_{n})}$

Para determinar la complejidad temporal de los algoritmos para el problema de decisión de la teoría existencial de los reales, es importante tener una medida del tamaño de la entrada. La medida más sencilla de este tipo es la longitud de una frase: es decir, el número de símbolos que contiene. ^[5] Sin embargo, para lograr un análisis más preciso del comportamiento de los algoritmos para este problema, es conveniente descomponer el tamaño de entrada en varias variables, separando el número de variables a cuantificar, el número de polinomios dentro la oración y el grado de estos polinomios. ^[8]

Ejemplos

La proporción áurea puede definirse como la raíz del polinomio . Este polinomio tiene dos raíces, de las cuales sólo una (la proporción áurea) es mayor que uno. Por tanto, la existencia de la proporción áurea puede expresarse mediante la frase ${\displaystyle \varphi }$ ${\displaystyle x^{2}-x-1}$

$${\displaystyle \exists X_{1}(X_{1}>1\wedge X_{1}\times X_{1}-X_{1}-1=0).}$$

trascendental

La desigualdad de medias aritmética y geométrica establece que, por cada dos números no negativos y , se cumple la siguiente desigualdad: ${\displaystyle x}$ ${\displaystyle y}$

$${\displaystyle {\frac {x+y}{2}}\geq {\sqrt {xy}}.}$$

${\displaystyle \exists X_{1}\exists X_{2}{\bigl (}X_{1}\geq 0\wedge X_{2}\geq 0\wedge (X_{1}+X_{2})\times (X_{1}+X_{2})<(X_{1}+X_{1})\times (X_{2}+X_{2}){\bigr )}.}$

La respuesta al problema de decisión de la teoría existencial de los reales, dada esta oración como entrada, es el valor booleano falso: no hay contraejemplos. Por tanto, esta frase no pertenece a la teoría existencial de los reales, a pesar de tener la forma gramatical correcta.

Algoritmos

El método de eliminación de cuantificadores de Alfred Tarski (1948) demostró que la teoría existencial de los reales (y más generalmente la teoría de los reales de primer orden) era algorítmicamente solucionable, pero sin un límite elemental a su complejidad. ^{[9] [6]} El método de descomposición algebraica cilíndrica , de George E. Collins (1975), mejoró la dependencia del tiempo a doblemente exponencial , ^{[9] [10]} de la forma

$${\displaystyle L^{3}(md)^{2^{O(n)}}}$$

^[8]Dima Grigoriev^{[8] [11] [12]} ${\displaystyle L}$ ${\displaystyle m}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle n}$

$${\displaystyle L(md)^{n^{2}}}$$

de , ^{[8] [13] [14] [15]} ${\displaystyle n}$

$${\displaystyle L\log L\log \log L(md)^{O(n)}.}$$

John CannyPSPACE^{[2] [9]}

La complejidad computacional asintótica de estos algoritmos puede ser engañosa, porque en la práctica sólo pueden ejecutarse con entradas de tamaño muy pequeño. En una comparación de 1991, Hoon Hong estimó que el procedimiento doblemente exponencial de Collins sería capaz de resolver un problema cuyo tamaño se describe estableciendo todos los parámetros anteriores en 2, en menos de un segundo, mientras que los algoritmos de Grigoriev, Vorbjov y Renegar en cambio, tomaría más de un millón de años. ^[8] En 1993, Joos, Roy y Solernó sugirieron que debería ser posible hacer pequeñas modificaciones a los procedimientos de tiempo exponencial para hacerlos más rápidos en la práctica que la decisión algebraica cilíndrica, así como más rápidos en teoría. ^[16] Sin embargo, a partir de 2009, todavía se daba el caso de que los métodos generales para la teoría de los reales de primer orden seguían siendo superiores en la práctica a los algoritmos exponenciales individuales especializados en la teoría existencial de los reales. ^[3]

problemas completos

Varios problemas de complejidad computacional y teoría de grafos geométricos pueden clasificarse como completos para la teoría existencial de los reales. Es decir, cada problema en la teoría existencial de los reales tiene una reducción de muchos uno en tiempo polinomial a una instancia de uno de estos problemas y, a su vez, estos problemas son reducibles a la teoría existencial de los reales. ^{[4] [17]}

Varios problemas de este tipo se refieren al reconocimiento de gráficos de intersección de un determinado tipo. En estos problemas, la entrada es un gráfico no dirigido ; El objetivo es determinar si las formas geométricas de una determinada clase de formas se pueden asociar con los vértices del gráfico de tal manera que dos vértices sean adyacentes en el gráfico si y sólo si sus formas asociadas tienen una intersección no vacía. Los problemas de este tipo que son completos para la teoría existencial de los reales incluyen el reconocimiento de gráficas de intersección de segmentos de línea en el plano, ^{[4] [18] [5]} reconocimiento de gráficas de disco unitario , ^[19] y reconocimiento de gráficas de intersección de conjuntos convexos en el plano. ^[4]

Para gráficos dibujados en el plano sin cruces, el teorema de Fáry establece que se obtiene la misma clase de gráficos planos independientemente de si los bordes del gráfico se dibujan como segmentos de línea recta o como curvas arbitrarias. Pero esta equivalencia no es válida para otros tipos de dibujo. Por ejemplo, aunque el número de cruces de un gráfico (el número mínimo de cruces en un dibujo con bordes arbitrariamente curvos) puede determinarse en NP, es completo para la teoría existencial de los reales determinar si existe un dibujo que logra un determinado limitado al número de cruce rectilíneo (el número mínimo de pares de aristas que se cruzan en cualquier dibujo con aristas dibujadas como segmentos de línea recta en el plano). ^{[4] [20]} También es completo para la teoría existencial de los reales probar si un gráfico dado se puede dibujar en el plano con aristas rectas y con un conjunto dado de pares de aristas como cruces, o de manera equivalente, si una El dibujo curvo con cruces se puede enderezar de forma que conserve sus cruces. ^[21]

Otros problemas completos para la teoría existencial de los reales incluyen:

• el problema de la galería de arte de encontrar el menor número de puntos desde los cuales todos los puntos de un polígono dado son visibles. ^[22]
• entrenamiento de redes neuronales. ^[23]
• el problema de empaquetamiento de decidir si un conjunto dado de polígonos cabe en un contenedor cuadrado dado. ^[24]
• reconocimiento de gráficos de distancias unitarias y prueba de si la dimensión o dimensión euclidiana de un gráfico es como máximo un valor dado. ^[9]
• capacidad de estiramiento de pseudolíneas (es decir, dada una familia de curvas en el plano, determinar si son homeomórficas con respecto a una disposición de líneas ); ^{[4] [25] [26]}
• satisfacibilidad tanto débil como fuerte de la lógica cuántica geométrica en cualquier dimensión fija >2; ^[27]
• Modelo de cadenas de Markov de intervalo de verificación con respecto a autómatas inequívocos. ^[28]
• el problema algorítmico de Steinitz (dada una red , determinar si es la red de caras de un politopo convexo ), incluso cuando está restringido a politopos de 4 dimensiones; ^{[29] [30]}
• espacios de realización de disposiciones de ciertos cuerpos convexos ^[31]
• diversas propiedades de los equilibrios de Nash de los juegos multijugador ^{[32] [33] [34]}
• incorporar un complejo abstracto determinado de triángulos y cuadriláteros en un espacio euclidiano tridimensional; ^[17]
• incrustar múltiples gráficos en un vértice compartido establecido en el plano para que todos los gráficos se dibujen sin cruces; ^[17]
• reconocer los gráficos de visibilidad de conjuntos de puntos planos; ^[17]
• (afín proyectivo o no trivial) satisfacibilidad de una ecuación entre dos términos sobre el producto cruzado ; ^[35]
• determinar el número mínimo de pendiente de un dibujo que no se cruza de un gráfico plano ; ^[36]
• reconocer gráficas que se pueden dibujar con todos los cruces en ángulo recto ; ^[37]
• el problema de evaluación parcial para el lenguaje de consulta matricial propio MATLANG+. ^[38]
• El problema de completar matrices de rango bajo . ^[39]

En base a esto, la clase de complejidad se ha definido como el conjunto de problemas que tienen una reducción muchos-uno en tiempo polinomial a la teoría existencial de los reales. ^[4] ${\displaystyle \exists \mathbb {R} }$

Ver también

• El décimo problema de Hilbert , sobre la (indecidible) teoría existencial de los números enteros

Referencias

1. Basu, Saugata; Pollack, Richard ; Roy, Marie-Françoise (2006), "Teoría existencial de los reales", Algoritmos en geometría algebraica real , Algoritmos y computación en matemáticas, vol. 10 (2ª ed.), Springer-Verlag, págs. 505–532, doi :10.1007/3-540-33099-2_14, ISBN 978-3-540-33098-1.
2. Canny, John (1988), "Algunos cálculos algebraicos y geométricos en PSPACE", Actas del vigésimo simposio anual de ACM sobre teoría de la computación (STOC '88, Chicago, Illinois, EE. UU.) , Nueva York, NY, EE. UU.: ACM , págs. 460–467, doi : 10.1145/62212.62257 , ISBN 0-89791-264-0, S2CID  14535463
3. Passmore, Grant Olney; Jackson, Paul B. (2009), "Técnicas de decisión combinadas para la teoría existencial de los reales", Matemáticas informáticas inteligentes: 16º Simposio, Calculemus 2009, 8ª Conferencia Internacional, MKM 2009, celebrada como parte de CICM 2009, Grand Bend, Canadá , 6 al 12 de julio de 2009, Actas, Parte II, Apuntes de conferencias sobre informática , vol. 5625, Springer-Verlag, págs. 122–137, doi :10.1007/978-3-642-02614-0_14, hdl : 20.500.11820/b2cc91c8-6b87-4146-bab6-a2021b3006b2 , S2CID  1160351.
4. Schaefer, Marcus (2010), "Complejidad de algunos problemas geométricos y topológicos" (PDF) , dibujo gráfico, 17º Simposio Internacional, GD 2009, Chicago, IL, EE. UU., septiembre de 2009, artículos revisados , notas de conferencias en informática, vol. 5849, Springer-Verlag, págs. 334–344, doi : 10.1007/978-3-642-11805-0_32.
5. Matoušek, Jiří (2014), "Gráficos de intersección de segmentos y ", arXiv : 1406.2636 [cs.CG] ${\displaystyle \exists \mathbb {R} }$
6. Tarski, Alfred (1948), Un método de decisión para álgebra y geometría elementales , RAND Corporation, Santa Mónica, California, MR  0028796.
7. Matiyasevich, Yu. V. (2006), "El décimo problema de Hilbert: ecuaciones diofánticas en el siglo XX", Acontecimientos matemáticos del siglo XX , Berlín: Springer-Verlag, págs. 185-213, Bibcode :2006metc.book.....A, doi :10.1007/3-540-29462-7_10, SEÑOR  2182785.
8. Hong, Hoon (11 de septiembre de 1991), Comparación de varios algoritmos de decisión para la teoría existencial de los reales, Informe técnico, vol. 91–41, RISC Linz^{[ enlace muerto permanente ]} .
9. Schaefer, Marcus (2013), "Realizabilidad de gráficos y vínculos", en Pach, János (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer-Verlag, págs. 461–482, doi :10.1007/978-1 -4614-0110-0_24.
10. Collins, George E. (1975), "Eliminación de cuantificadores para campos cerrados reales mediante descomposición algebraica cilíndrica", Teoría de autómatas y lenguajes formales (Second GI Conf., Kaiserslautern, 1975) , Lecture Notes in Computer Science , vol. 33, Berlín: Springer-Verlag, págs. 134–183, SEÑOR  0403962.
11. Grigor'ev, D. Yu. (1988), "Complejidad de decidir el álgebra de Tarski", Journal of Symbolic Computation , 5 (1–2): 65–108, doi : 10.1016/S0747-7171(88)80006-3 , MR  0949113.
12. Grigor'ev, D. Yu. ; Vorobjov, NN Jr. (1988), "Resolución de sistemas de desigualdades polinómicas en tiempo subexponencial" (PDF) , Journal of Symbolic Computation , 5 (1–2): 37–64, doi :10.1016/S0747-7171(88)80005 -1, SEÑOR  0949112, S2CID  39376619.
13. Renegar, James (1992), "Sobre la complejidad computacional y la geometría de la teoría de los reales de primer orden. I. Introducción. Preliminares. La geometría de conjuntos semialgebraicos. El problema de decisión para la teoría existencial de los reales" , Revista de Computación Simbólica , 13 (3): 255–299, doi : 10.1016/S0747-7171(10)80003-3 , SEÑOR  1156882.
14. Renegar, James (1992), "Sobre la complejidad computacional y la geometría de la teoría de los reales de primer orden. II. El problema de decisión general. Preliminares para la eliminación de cuantificadores", Journal of Symbolic Computation , 13 (3): 301– 327, doi : 10.1016/S0747-7171(10)80004-5 , SEÑOR  1156883.
15. Renegar, James (1992), "Sobre la complejidad computacional y la geometría de la teoría de los reales de primer orden. III. Eliminación del cuantificador", Journal of Symbolic Computation , 13 (3): 329–352, doi : 10.1016/S0747 -7171(10)80005-7 , SEÑOR  1156884.
16. Heintz, Joos; Roy, Marie-Françoise ; Solernó, Pablo (1993), "Sobre la complejidad teórica y práctica de la teoría existencial de los reales", The Computer Journal , 36 (5): 427–431, doi : 10.1093/comjnl/36.5.427 , MR  1234114.
17. Cardinal, Jean (diciembre de 2015), "Columna 62 de geometría computacional", SIGACT News , 46 (4): 69–78, doi :10.1145/2852040.2852053, S2CID  17276902.
18. Kratochvíl, enero ; Matoušek, Jiří (1994), "Gráficos de intersección de segmentos", Journal of Combinatorial Theory, Serie B , 62 (2): 289–315, doi : 10.1006/jctb.1994.1071 , MR  1305055.
19. Kang, Ross J.; Müller, Tobias (2011), "Representaciones de gráficos con esferas y productos escalables", Actas del vigésimo séptimo simposio anual sobre geometría computacional (SCG'11), 13 al 15 de junio de 2011, París, Francia , págs..
20. Bienstock, Daniel (1991), "Algunos problemas de números de cruce demostrablemente difíciles", Geometría discreta y computacional , 6 (5): 443–459, doi : 10.1007/BF02574701 , MR  1115102, S2CID  38465081.
21. Kynčl, Jan (2011), "Realización simple de gráficos topológicos abstractos completos en P", Geometría computacional y discreta , 45 (3): 383–399, doi : 10.1007 / s00454-010-9320-x , MR  2770542, S2CID  12419381.
22. Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2022), "El problema de la galería de arte está completo", Journal of the ACM , 69 (1): A4:1–A4:70, doi :10.1145/3486220, MR  4402363 ${\displaystyle \exists {\mathbb {R}}}$
23. Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann (2021), "El entrenamiento de redes neuronales es ∃ R {\displaystyle \exists \mathbb {R} } -completo", en Ranzato, Marc'Aurelio; Beygelzimer, Alina; Dauphin, Yann N.; Liang, Percy; Vaughan, Jennifer Wortman (eds.), Avances en sistemas de procesamiento de información neuronal 34: Conferencia anual sobre sistemas de procesamiento de información neuronal 2021, NeurIPS 2021, 6 al 14 de diciembre de 2021, virtual , págs. 18293–18306, arXiv : 2102.09798
24. Abrahamsen, Mikkel; Miltzow, Tillmann; Seiferth, Nadja (2020), "Framework for -completeness of two-dimensional packaging issues", 61.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2020, Durham, Carolina del Norte, EE. UU., 16 al 19 de noviembre de 2020 , IEEE, págs. 1014–1021, arXiv : 2004.07558 , doi : 10.1109/FOCS46700.2020.00098, S2CID  216045462 ${\displaystyle \exists \mathbb {R} }$
25. Mnëv, NE (1988), "Los teoremas de universalidad sobre el problema de clasificación de variedades de configuración y variedades de politopos convexos", Topología y geometría — Seminario Rohlin , Lecture Notes in Mathematics , vol. 1346, Berlín: Springer-Verlag, págs. 527–543, doi :10.1007/BFb0082792, MR  0970093.
26. Shor, Peter W. (1991), "La capacidad de estiramiento de las pseudolíneas es NP-dura", Geometría aplicada y matemáticas discretas , Serie DIMACS en Matemáticas discretas e informática teórica, vol. 4, Providence, RI: Sociedad Matemática Estadounidense , págs. 531–554, SEÑOR  1116375.
27. Herrmann, cristiano; Ziegler, Martin (2016), "Complejidad computacional de la satisfacción cuántica", Journal of the ACM , vol. 63, arXiv : 1004.1696 , doi : 10.1145/2869073, S2CID  2253943.
28. Benedikt, Michael; Lenhardt, Rastislav; Worrell, James (2013), "Verificación del modelo LTL de cadenas de intervalo de Markov", Herramientas y algoritmos para la construcción y análisis de sistemas. TACAS 2013 , Apuntes de conferencias sobre informática, vol. 7795, págs. 32–46, doi :10.1007/978-3-642-36742-7_3
29. Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; Blanco, Neil; Ziegler, Günter M. (1993), Matroides orientadas , Enciclopedia de las matemáticas y sus aplicaciones, vol. 46, Cambridge: Cambridge University Press, Corolario 9.5.10, pág. 407, ISBN 0-521-41836-4, señor  1226888.
30. Richter-Gebert, Jürgen; Ziegler, Günter M. (1995), "Los espacios de realización de 4 politopos son universales", Boletín de la Sociedad Matemática Estadounidense , Nueva Serie, 32 (4): 403–412, arXiv : math/9510217 , Bibcode : 1995math.. ...10217R, doi :10.1090/S0273-0979-1995-00604-X, SEÑOR  1316500, S2CID  7940964.
31. Dobbins, Michael Gene; Holmsen, Andreas; Hubard, Alfredo (2017), "Realización de espacios de disposiciones de cuerpos convexos", Geometría discreta y computacional , 58 (1): 1–29, arXiv : 1412.0371 , doi :10.1007/s00454-017-9869-8, MR  3658327, S2CID  39856606.
32. Garg, yugal; Mehta, Ruta; Vazirani, Vijay V .; Yazdanbod, Sadra (2015), "ETR-Completitud para versiones de decisión de equilibrios de Nash multijugador (simétricos), Proc. 42º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) , Apuntes de conferencias en Ciencias de la Computación, vol. 9134, Springer, págs. 554–566, doi :10.1007/978-3-662-47672-7_45.
33. Bilo, Vittorio; Mavronicolas, Marios (2016), "Un catálogo de problemas de decisión completa ETR sobre equilibrios de Nash en juegos multijugador", Actas del 33º Simposio internacional sobre aspectos teóricos de la informática , LIPIcs, vol. 47, Schloss Dagstuhl--Leibnitz Zentrum fuer Informatik, págs. 17:1–17:13, doi :10.4230/LIPIcs.STACS.2016.17, ISBN 978-3-95977-001-9.
34. Bilo, Vittorio; Mavronicolas, Marios (2017), "ETR-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games", Actas del 34º Simposio internacional sobre aspectos teóricos de la informática, LIPIcs, vol. 66, Schloss Dagstuhl--Leibnitz Zentrum fuer Informatik, págs. 13:1–13:14, doi :10.4230/LIPIcs.STACS.2017.13, ISBN 978-3-95977-028-6.
35. Herrmann, cristiano; Sokoli, Johanna; Ziegler, Martin (2013), "La satisfacción de los términos de productos cruzados es completa para máquinas Blum-Shub-Smale politime reales no deterministas", Actas de la 6ª Conferencia sobre Máquinas, Computación y Universalidad (MCU'13) , vol. 128, arXiv : 1309.1043 , doi : 10.4204/EPTCS.128 , S2CID  2151889.
36. Hoffmann, Udo (2016), "El número de pendiente plana", Actas de la 28.ª Conferencia Canadiense sobre Geometría Computacional (CCCG 2016).
37. Schaefer, Marcus (2021), "RAC-drawability is -complete", Actas del 29º Simposio internacional sobre dibujo de gráficos y visualización de redes (GD 2021) , arXiv : 2107.11663 ${\displaystyle \exists \mathbb {R} }$
38. Brijder, Robert; Geerts, Floris; Van den Bussche, enero; Weerwag, Timmy (2019), "Sobre el poder expresivo de los lenguajes de consulta para matrices", Transacciones ACM en sistemas de bases de datos , ACM, 44 (4): 15:1–15:31, doi :10.1145/3331445, hdl : 1942 /30378 , S2CID  204714822.
39. Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2021), "Optimización cónica de proyección mixta: un nuevo paradigma para modelar restricciones de rango", Investigación de operaciones , 70 (6): 3321–3344, arXiv : 2009.10395 , doi : 10.1287/opre.2021.2182, S2CID  221836263.