Hilbert’s Tenth Problem for Fixed d and n
William I. Gasarch · Bulletin of the European Association for Theoretical Computer Science · 2021
Hilbert’s 10th problem, stated in modern terms, is Find an algorithm that will, given p 2 Z [ x 1 , . . . , x n ] , determine if there exists a 1 ,..., a n 2 Z such that p ( a 1 ,..., a n ) = 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.