La complejidad basada en información ( IBC ) estudia algoritmos óptimos y complejidad computacional para los problemas continuos que surgen en las ciencias físicas , la economía , la ingeniería y las finanzas matemáticas . IBC ha estudiado problemas continuos como integración de trayectorias , ecuaciones diferenciales parciales , sistemas de ecuaciones diferenciales ordinarias , ecuaciones no lineales , ecuaciones integrales , puntos fijos e integración de muy alta dimensión . Todos estos problemas involucran funciones (típicamente multivariadas) de una variable real o compleja . Como nunca se puede obtener una solución cerrada para los problemas de interés, hay que conformarse con una solución numérica. Dado que una función de una variable real o compleja no se puede ingresar en una computadora digital, la solución de problemas continuos implica información parcial . Para dar una ilustración sencilla, en la aproximación numérica de una integral, sólo están disponibles muestras del integrando en un número finito de puntos. En la solución numérica de ecuaciones diferenciales parciales sólo se pueden muestrear las funciones que especifican las condiciones de contorno y los coeficientes del operador diferencial. Además, esta información parcial puede resultar costosa de obtener. Finalmente, la información suele estar contaminada por el 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 cotizada, y aplicar los resultados para responder preguntas en diversas disciplinas. Ejemplos de tales disciplinas incluyen la física , la economía, las finanzas matemáticas, la visión por computadora , la teoría del control , la geofísica , las imágenes médicas , el pronóstico del tiempo y la predicción del clima , y la estadística . La teoría se desarrolla sobre espacios abstractos, típicamente espacios de Hilbert o Banach , mientras que las aplicaciones suelen ser para problemas multivariados.
Dado que la información es parcial y está contaminada, sólo se pueden obtener soluciones aproximadas. IBC estudia la complejidad computacional y los algoritmos óptimos para soluciones aproximadas en diversos entornos. Dado que el peor de los casos a menudo conduce a resultados negativos, como insolvencia e 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 aproximarnos 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 tenemos información parcial, podemos usar un argumento adversario para decirnos qué tan grande debe ser n para calcular una aproximación. Debido a estos argumentos basados en información, a menudo podemos obtener límites estrictos sobre la complejidad de los problemas continuos. Para 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 ingresar en la computadora. Por lo tanto, normalmente no existe ningún argumento adversario a nivel de información y rara vez se conoce la complejidad de un problema discreto.
El problema de integración univariante fue sólo para ilustración. Para muchas aplicaciones es importante la integración multivariante. El número de variables es de cientos o miles. El número de variables puede incluso ser infinito; entonces hablamos de integración de caminos. La razón por la que las integrales son importantes en muchas disciplinas es que ocurren cuando queremos conocer el comportamiento esperado de un proceso continuo. Véase, por ejemplo, la aplicación a las finanzas matemáticas 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 de orden (aquí estamos contando el número de evaluaciones de funciones y el número de operaciones aritméticas, por lo que esta es la complejidad temporal). Esto tomarí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 ocurre en casi todos los problemas continuos que se han investigado. ¿Cómo podemos intentar vencer la maldición? Hay dos posibilidades:
Las integrales de muy altas dimensiones son comunes en las 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. Recuerde que si se requiere una garantía en el peor de los casos, el tiempo es de unidades de tiempo de orden. Incluso si el error no es pequeño, digamos que se trata de unidades de tiempo. Los profesionales de las finanzas llevan mucho tiempo utilizando el método Monte Carlo (MC), un ejemplo de 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 utiliza secuencias de baja discrepancia, superaba al MC en uno a tres órdenes de magnitud. Los resultados fueron comunicados a varias entidades financieras de Wall Street, con considerable escepticismo inicial. 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, QMC se utiliza ampliamente en el sector financiero para valorar derivados financieros.
Estos resultados son empíricos; ¿Dónde entra 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 futuros son menos importantes que las variables que representan tiempos cercanos. Por tanto, las integrales no son isotrópicas. Sloan y Woźniakowski introdujeron la muy poderosa idea de espacios ponderados, que es una formalización de la observación anterior. Pudieron demostrar que con este conocimiento de dominio adicional, las integrales de alta dimensión que satisfacían ciertas condiciones eran manejables incluso en el peor de los casos. Por el contrario, el método de Monte Carlo sólo ofrece una seguridad estocástica. Véase Sloan y Woźniakowski ¿ Cuándo son eficientes los algoritmos cuasi-Monte Carlo para una integración de alta dimensión? J. Complexity 14, 1-33, 1998. ¿Para qué clases de integrales QMC es superior a MC? Este sigue siendo un importante problema de investigación.
Kiefer, Sard y Nikolskij pueden encontrar precursores del IBC en la década de 1950. En 1959, Traub tuvo la idea clave de que el algoritmo óptimo y la complejidad computacional de resolver un problema continuo dependían de la información disponible. Aplicó esta idea a la solución de ecuaciones no lineales , lo que inició el área de la teoría de la iteración óptima. Esta investigación fue publicada en la monografía de 1964 Métodos iterativos para la solución de ecuaciones.
El marco general para la complejidad basada en la información fue formulado 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 sugerencias sobre la extensa literatura, consulte Para obtener más información a continuación.
Hay varios premios para la investigación del IBC.
![{\displaystyle [f(t_{1}),\dots,f(t_{n})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d79bb60380e71b9d1fc49baaf93ef63b494fa92)
{{cite book}}: Mantenimiento CS1: 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.