[FOM] Quantified Diophantine Equatios

pax0@seznam.cz pax0 at seznam.cz
Thu Mar 6 07:17:24 EST 2008

According to Matiyasevich's theorem, every recursively enumerable set of
natural numbers is a set of solutions to an existentially quantified Diophantine equation.

What is the complexity (e.g. in terms of arithmetical hierarchy) of next levels of quantification of Diophantine equations, like

{ n \in N | (All x1 ... All xj) (Ex xj+1 ... Ex xk) f(x1,...,xj,...,xk,n)=0 } 

and in general with Sigma_n prefixes,
for a polynomial f with integer coefficients?

Thank you, J.P.

More information about the FOM mailing list