Hilbert's tenth problem

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation (a polynomial equation with integer coefficients and a finite number of unknowns), can decide whether the equation has a solution with all unknowns taking integer values.

For example, the Diophantine equation ${\displaystyle 3x^{2}-2xy-y^{2}z-7=0}$ has an integer solution: ${\displaystyle x=1,\ y=2,\ z=-2}$. By contrast, the Diophantine equation ${\displaystyle x^{2}+y^{2}+1=0}$ has no such solution.

Hilbert's tenth problem has been solved, and it has a negative answer: such a general algorithm cannot exist. This is the result of combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson that spans 21 years, with Matiyasevich completing the theorem in 1970.^[1] The theorem is now known as Matiyasevich's theorem or the MRDP theorem (an initialism for the surnames of the four principal contributors to its solution).

When all coefficients and variables are restricted to be positive integers, the related problem of polynomial identity testing becomes a decidable (exponentiation-free) variation of Tarski's high school algebra problem, sometimes denoted ${\displaystyle {\overline {HSI}}.}$^[2]