Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy (Q5943088)

Two problems are analyzed. The first one refers to the decidability of the following sentence: Given a polynomial \(f\) with integer coefficients in \(v,x,y\), there is an integer \(v\) such that for any integer \(x\) there is an integer \(y\) for which \(f(v,x,y)=0\). It is proved that this problem is coNP. The second problem refers to the decidability of the following sentence: Given \(m\) polynomials \(f_1,\ldots,f_m\) with integer coefficients in \(x_1,\ldots x_n\) and \(m\geq n\), there is a rational solution to \(f_1=\cdots =f_m=0\). It is proved that this problem can be done with the complexity class \(P^{NP^{NP}}\).