HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is the runtime of the 'Risch Algorithm'?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewhatruntimealgorithmrisch

Problem

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'?

Solution

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.

Context

StackExchange Computer Science Q#74798, answer score: 3

Revisions (0)

No revisions yet.