In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n₁, ..., n_j, x₁, ..., x_k) such that a tuple (n₁, ..., n_j) of integers is in S if and only if there exist some integers x₁, ..., x_k with f(n₁, ..., n_j, x₁, ..., x_k) = 0. (Such a polynomial equation over the integers is also called a Diophantine equation.) In other words, a Diophantine set is a set of the form

where f is a polynomial function with integer coefficients.

Matiyasevich's theorem, published in 1970, states that a set of integers is Diophantine if and only if it is recursively enumerable. A set S is recursively enumerable precisely if there is an algorithm that, when given an integer, eventually halts if that input is a member of S and otherwise runs forever.

Matiyasevich's theorem effectively settled Hilbert's tenth problem.