the Risch algorithm
/ RISH /
Generations of students integrate by hunting for a trick: try a substitution, try parts, try a table, and hope. The Risch algorithm replaces the hunting with certainty. Published by Robert Risch in 1968, it is a decision procedure for integration: given an elementary function, it does not merely try to find an antiderivative — it is guaranteed either to produce one in closed form or to PROVE that no elementary antiderivative exists. It turns 'I couldn't find it' into the far stronger 'there is none'.
The key insight is structural, not a bag of tricks. Risch builds the integrand inside a 'differential field' — a tower of extensions where each new layer adds exactly one transcendental element (an exponential like e^x or a logarithm like log(x)) on top of the rational functions. Within this rigid algebraic structure, the question 'does an elementary antiderivative exist, and what is it?' becomes a sequence of solvable algebraic conditions on the coefficients: you posit the general shape an antiderivative must take in the same field, then solve for it, and the conditions either succeed (yielding the integral) or are provably unsatisfiable (proving none exists). It rests on Liouville's theorem, which sharply constrains what an elementary antiderivative can look like, and it is the engine of the integrate command in serious computer-algebra systems.
The Risch algorithm matters as the theoretical capstone of symbolic integration — it is why a CAS can confidently say exp(-x^2) has no elementary integral rather than just failing. The honest caveats are real. The full algorithm is enormously intricate; no system implements it completely, because it bottoms out in sub-problems (deciding whether certain constants are zero) that touch the undecidable zero-equivalence problem. Real systems implement a large practical fragment plus heuristics and tables. And it is confined to elementary functions: extend the question to special functions and the clean decision procedure no longer applies.
Ask a CAS for the integral of exp(x^2). The Risch machinery, after building the differential field generated by exp(x^2), determines that no rational function R can make d/dx (R * exp(x^2)) equal exp(x^2). It therefore returns a proof-backed verdict: no elementary antiderivative exists (the answer is named with the imaginary error function erfi).
Risch decides existence: a closed-form integral, or a proof there is none.
No computer-algebra system implements the Risch algorithm in full, because its constant-zero-testing subproblem runs into the undecidable zero-equivalence problem. In practice systems use a large fragment plus heuristics — so a CAS occasionally fails to integrate something that is in fact elementary.