Limitations to algorithm solvability: Galois methods and models of computation
Chanderjit Bajaj · 1986
We use simple argwnents from Galois theory to prove the impossibility of exact algorilhms for problems under various models of computation.In particular we show that lhere exist applied computational problems for which there are no closed form solutions over models such as Q(+,", .,/,v), Q (+, _, '10, /, tv), and Q(+, -, '1<,/, k...J, q(x», where Q is the field of rationals and q(x)eQ[x] are polynomials with non-solvable Galois groups.