[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