5
$\begingroup$

I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so.

https://en.wikipedia.org/wiki/Risch_algorithm

Does anyone know where I would be able to find the runtime of the 'Risch Algorithm'?

$\endgroup$
3
$\begingroup$

The Risch algorithm is undecidable by Richardson Theorem if absolute value is allowed or semi-undecidable with $\log_2, \pi, e^x, \sin x$.
Akitoshi Kawamura in his dissertation Computational Complexity in Analysis and Geometry has proved that integration is $\#P{-}complete$ operation.

There are multiple modifications of the Risch algorithm, but still nobody have implemented the full algorithm (source: Wolfram, survey over CAS systems) in algebraic case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.