Hay varios problemas al intentar responder esa pregunta.
Para que algo se clasifique como “un problema NP” o no, debe ser un problema de decisión con un parámetro de tamaño específico (generalmente llamado “[matemáticas] n [/ matemáticas]”), para que podamos examinar si las instancias de ese problema de decisión puede verificarse en el tiempo polinomial en [math] n [/ math].
El término “resolver integrales” no es de ninguna manera obvio. Presumiblemente, quiere decir algo como esto: un programa que recibe como entrada una función elemental descrita de alguna manera formal, y produce como salida una función elemental que es una antiderivada de la entrada. Podemos suponer que el parámetro de tamaño [math] n [/ math] es una indicación de la longitud de la expresión de entrada.
- Si una persona tuviera un nuevo modelo de física fundacional de calidad nacido de la informática, no de las matemáticas, ¿cuál sería la mejor manera de presentarlo?
- ¿Cómo podemos abordar para resolver el problema de 'Infinite House of Pancakes' de Google Code Jam 2015?
- Cómo interpretar 'lift' y 'odds ratio' en las reglas de asociación
- ¿Qué es 7/6 en binario?
- ¿Qué es Stanford M&CS?
Entonces, antes que nada, ese no es un problema de decisión. Se supone que los problemas de decisión solo responden “sí” o “no” en una entrada dada. Esto se puede solucionar cambiando la pregunta para que sea sobre la clase FNP en lugar de NP. FNP es el análogo de NP para problemas de función, mientras que NP se aplica solo a problemas de decisión.
Ingenuamente, puede argumentar que verificar una respuesta al problema de calcular una antiderivada se puede hacer de manera muy eficiente, ya que simplemente implica el cálculo de una derivada. Esto ciertamente se puede hacer en tiempo polinómico. Por lo tanto, parece que la integración simbólica de las funciones elementales está realmente en FNP.
Sin embargo, entonces se queda con el problema de decidir si dos funciones elementales explícitas son las mismas: la entrada y la derivada calculada de la salida. Ese problema es indecidible . No es una cuestión de eficiencia: no hay ningún algoritmo para hacer esto en absoluto . Entonces, el problema de calcular integrales simbólicas tiene problemas más grandes que estar en FNP o no: no es manejable algorítmicamente.
En la práctica, existen buenos algoritmos que manejan la integración simbólica de manera bastante eficiente y devuelven la respuesta correcta en la mayoría de los casos. Sin embargo, no tiene sentido preguntar si tales algoritmos están o no en NP o FNP, ya que no son algoritmos en absoluto: son semi-algoritmos que solo funcionan con éxito en un subconjunto de sus entradas, y ese subconjunto no está reconocible por cualquier algoritmo.
