Diophantine equations and complexity classes
This paper, Computational complexities of Diophantine equations with parameters by Tung, proves co-NP-completeness of a variant with parameters over natural numbers.