Hilbert’s Tenth Problem for Fixed d and n

Abstract

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.