La complejidad basada en la información ( IBC ) estudia los algoritmos óptimos y la complejidad computacional para los problemas continuos que surgen en las ciencias físicas , la economía , la ingeniería y las finanzas matemáticas . La IBC ha estudiado problemas continuos como la integración de trayectorias , las ecuaciones diferenciales parciales , los sistemas de ecuaciones diferenciales ordinarias , las ecuaciones no lineales , las ecuaciones integrales , los puntos fijos y la integración de muy alta dimensión . Todos estos problemas involucran funciones (normalmente multivariadas) de una variable real o compleja . Como nunca se puede obtener una solución de forma cerrada para los problemas de interés, hay que conformarse con una solución numérica. Como una función de una variable real o compleja no se puede introducir en una computadora digital, la solución de problemas continuos involucra información parcial . Para dar una ilustración sencilla, en la aproximación numérica de una integral, solo se dispone de muestras del integrando en un número finito de puntos. En la solución numérica de ecuaciones diferenciales parciales, solo se pueden muestrear las funciones que especifican las condiciones de contorno y los coeficientes del operador diferencial. Además, esta información parcial puede ser costosa de obtener. Finalmente, la información a menudo está contaminada por ruido.
El objetivo de la complejidad basada en la información es crear una teoría de la complejidad computacional y algoritmos óptimos para problemas con información parcial, contaminada y con precio, y aplicar los resultados para responder preguntas en varias disciplinas. Ejemplos de tales disciplinas incluyen física , economía, finanzas matemáticas, visión por computadora , teoría de control , geofísica , imágenes médicas , pronóstico del tiempo y predicción del clima , y estadística . La teoría se desarrolla sobre espacios abstractos, típicamente espacios de Hilbert o Banach , mientras que las aplicaciones son generalmente para problemas multivariados.
Como la información es parcial y está contaminada, solo se pueden obtener soluciones aproximadas. El IBC estudia la complejidad computacional y los algoritmos óptimos para soluciones aproximadas en diversos entornos. Dado que el peor de los casos suele conducir a resultados negativos, como la imposibilidad de solución y la intratabilidad, también se estudian entornos con garantías más débiles, como el promedio, el probabilístico y el aleatorio. Un área bastante nueva de investigación del IBC es la computación cuántica continua .
Ilustramos algunos conceptos importantes con un ejemplo muy simple, el cálculo de
Para la mayoría de los integrandos no podemos utilizar el teorema fundamental del cálculo para calcular la integral analíticamente; tenemos que aproximarla numéricamente. Calculamos los valores de en n puntos
Los n números son la información parcial sobre el integrando verdadero. Combinamos estos n números mediante un algoritmo combinatorio para calcular una aproximación a la integral. Consulte la monografía Complejidad e información para obtener más detalles.
Como sólo disponemos de información parcial, podemos utilizar un argumento adversario para saber qué tan grande debe ser n para calcular una aproximación. Gracias a estos argumentos basados en la información, a menudo podemos obtener límites estrictos sobre la complejidad de los problemas continuos. En el caso de problemas discretos, como la factorización de números enteros o el problema del viajante, tenemos que conformarnos con conjeturas sobre la jerarquía de complejidad. La razón es que la entrada es un número o un vector de números y, por lo tanto, se puede introducir en la computadora. Por lo tanto, normalmente no hay argumento adversario a nivel de información y rara vez se conoce la complejidad de un problema discreto.
El problema de integración univariante se presentó únicamente a modo de ejemplo. La integración multivariante es significativa para muchas aplicaciones. El número de variables se encuentra en cientos o miles. El número de variables puede incluso ser infinito; en ese caso, hablamos de integración de trayectorias. La razón por la que las integrales son importantes en muchas disciplinas es que se presentan cuando queremos conocer el comportamiento esperado de un proceso continuo. Véase, por ejemplo, la aplicación a las finanzas matemáticas que se muestra a continuación.
Supongamos que queremos calcular una integral en d dimensiones (las dimensiones y las variables se usan indistintamente) y que queremos garantizar un error como máximo para cualquier integrando en alguna clase. Se sabe que la complejidad computacional del problema es del orden de (aquí contamos el número de evaluaciones de funciones y el número de operaciones aritméticas, por lo que esta es la complejidad temporal). Esto llevaría muchos años incluso para valores modestos de La dependencia exponencial de d se llama la maldición de la dimensionalidad . Decimos que el problema es intratable.
Hemos planteado la maldición de la dimensionalidad para la integración, pero la dependencia exponencial de d se da en casi todos los problemas continuos que se han investigado. ¿Cómo podemos intentar vencer la maldición? Hay dos posibilidades:
Las integrales de dimensiones muy altas son comunes en finanzas. Por ejemplo, calcular los flujos de efectivo esperados para una obligación hipotecaria garantizada (CMO) requiere el cálculo de una serie de integrales dimensionales, siendo la cantidad de meses en años. Recordemos que si se requiere una garantía del peor caso, el tiempo es del orden de unidades de tiempo. Incluso si el error no es pequeño, digamos que es de unidades de tiempo. Las personas en finanzas han estado usando durante mucho tiempo el método de Monte Carlo (MC), un ejemplo de un algoritmo aleatorio. Luego, en 1994, un grupo de investigación de la Universidad de Columbia (Papageorgiou, Paskov, Traub, Woźniakowski) descubrió que el método cuasi-Monte Carlo (QMC) que usa secuencias de baja discrepancia superaba al MC en uno a tres órdenes de magnitud. Los resultados se informaron a una serie de finanzas de Wall Street con un escepticismo inicial considerable. Los resultados fueron publicados por primera vez por Paskov y Traub , Faster Valuation of Financial Derivatives , Journal of Portfolio Management 22, 113-120. Hoy en día, el QMC se utiliza ampliamente en el sector financiero para valorar derivados financieros.
Estos resultados son empíricos; ¿dónde entra en juego la complejidad computacional? QMC no es una panacea para todas las integrales de alta dimensión. ¿Qué tienen de especial los derivados financieros? He aquí una posible explicación. Las dimensiones en el CMO representan tiempos futuros mensuales. Debido al valor descontado del dinero, las variables que representan tiempos para el futuro son menos importantes que las variables que representan tiempos cercanos. Por lo tanto, las integrales no son isotrópicas. Sloan y Woźniakowski introdujeron la idea muy poderosa de los espacios ponderados, que es una formalización de la observación anterior. Pudieron demostrar que con este conocimiento adicional del dominio, las integrales de alta dimensión que satisfacen ciertas condiciones eran manejables incluso en el peor de los casos. En contraste, el método de Monte Carlo solo brinda una garantía estocástica. Consulte Sloan y Woźniakowski When are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integration? J. Complexity 14, 1-33, 1998. ¿Para qué clases de integrales es QMC superior a MC? Este sigue siendo un importante problema de investigación.
Los precursores del IBC se pueden encontrar en la década de 1950 por Kiefer, Sard y Nikolskij. En 1959, Traub tuvo la idea clave de que el algoritmo óptimo y la complejidad computacional de la solución de un problema continuo dependían de la información disponible. Aplicó esta idea a la solución de ecuaciones no lineales , lo que dio inicio al área de la teoría de iteración óptima. Esta investigación se publicó en la monografía de 1964 Métodos iterativos para la solución de ecuaciones.
La configuración general de la complejidad basada en la información fue formulada por Traub y Woźniakowski en 1980 en Una teoría general de algoritmos óptimos. Para obtener una lista de monografías más recientes y referencias a la extensa literatura, consulte Más información a continuación.
Hay una serie de premios para la investigación del IBC.
![{\displaystyle [f(t_{1}),\puntos ,f(t_{n})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d79bb60380e71b9d1fc49baaf93ef63b494fa92)
{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )Se pueden encontrar bibliografías extensas en las monografías N (1988), TW (1980), TWW (1988) y TW (1998). El sitio web del IBC tiene una base de datos con capacidad de búsqueda de unos 730 artículos.