From Algebra to Computational Algorithms: Kolmogorov and Hilbert’s Problem 13

Problem 13 of Hilbert’s famous twenty-three is the most easily understood of the collection. The truth of Hilbert’s conjecture concerning the resolution of his problem was intuitively pleasing and widely-held: roughly stated, the number of variables in an equation is a measure of the complexity of the equation. In 1957 a nineteen year old student of Andrey Kolmogorov, Vladimir Arnold, proved that two variables suffice. That is, any function of more than two variables can be recast as a function of only two variables. From Algebra to Computational Algorithms recounts the history of Problem 13, elucidates Arnold’s surprising result, and explores some of the applications of the result to problems in computer science.