¿Cómo se determina la clase de complejidad de un problema como la resolución de una integral?

Question

Las clases P y NP se refieren a problemas de decisión, pero ¿qué pasa con los problemas de cálculo, concretamente con el cálculo de una integral? ¿Cómo se puede averiguar si una determinada clase de integrales está en P o en NP? ¿Se puede reformular algo así en términos de un problema de decisión? ¿O hay otro método indirecto?

Answer 1

No estoy seguro de que esta sea la respuesta que buscas, pero existe un algoritmo general para resolver integrales indefinidas llamado Algoritmo Risch . Básicamente, dado un conjunto de funciones elementales (polinomios, exponenciales, logaritmos, sen, cos, etc.) se puede escribir la integral de una función compuesta por funciones elementales en una forma normal. No tengo muy claro cuándo y dónde entra la decidibilidad (quizá un buen punto de partida sea el Sección de la Wikipedia al respecto ) pero parece que como un paso en el algoritmo de Risch está decidiendo el problema constante que se desconoce tener un algoritmo para ello. Desde la página de Wikipedia, se sabe que la adición de la función de valor absoluto hace que el problema indecidible ( Teorema de Richardson ).

Si se restringe a integrales definidas, entonces sólo decidir si una integral es 0 o no puede ser NP-Completo como la siguiente representación integral de la Problema de partición de números espectáculos:

Dado $n$ números, $(a_0, a_1, \cdots, a_{n-1})$ en el rango de $1$ a $M$ , encuentra si la siguiente integral es cero o no: $$ \frac{1}{2 \pi} \int_{-\pi}^{\pi}\ \ \prod_{k=0}^{n-1}(e^{i a_k \theta } + e^{ - i a_k \theta }) d\theta $$

Obsérvese que cada término del producto expandido será una combinación de todos los $a_k$ 's. Si una de las combinaciones del exponente suma 0, ese término se evaluará como un número positivo. Dado que el $a_k$ son enteros, si el término del exponente no suma 0, la integral se evaluará a 0. Todos los términos con un exponente distinto de cero desaparecen, mientras que todos los términos con un exponente 0 cuentan por 1, proporcionando así una función de "recuento" de todas las posibles soluciones.

Si uno quiere encontrar el valor real de esa integral, entonces este problema se convierte en $\#P$ .

Answer 2

Hay que utilizar un modelo de tipo superior para hablar fielmente de la complejidad y la computabilidad de los operadores en análisis como la integración. Quizás quieras consultar la tesis de Akitoshi Kawamura " Complejidad computacional en análisis y geometría ". Demuestra que la integración es $\mathsf{\#P\text{-}complete}$ operador.