Hilbert’s Tenth Problem for Fixed d and n

William Gasarch, The Algorithmics Column by Thomas Erlebach


Hilbert’s 10th problem, stated in modern terms, is

Find an algorithm that will, given p 2 Z[x1, . . . , xn], determine if there exists a1,...,an 2 Z such that p(a1,...,an) = 0.

Davis, Putnam, Robinson, and Matiyasevich showed that there is no such algorithm. But what if we bound the degree of the polynomial? The number of variables? This paper surveys what is known for these cases.

Full Text:



  • There are currently no refbacks.