The author analyzes the solvability and computational complexity of Diophantine equations with parameters over an algebraic integer ring (AIR); the question is whether, for a polynomial f , the sentence
∀ x 1 ... ∀ x n ∃ y f ( x 1 ,..., x n , y ) = 0
is true. Calling it an ∀ n ∃ equation, the author proves that the solvability of an ∀ n ∃ equation over a specific AIR is co–NP-complete, but its solvability over all AIRs is in P. Calling a sentence ∀ n ∃ y &fgr; ( x , y ) an ∀∃ sentence if &fgr; contains no quantifiers and no free variables except x and y , and &fgr; is in conjunctive (or disjunctive) normal form, Tung also proves that the decision problem for the truth of ∀∃ sentences over specific AIRs is co–NP-complete, but the decision problem for ∀∃ sentences over all AIRs is in P.
-sparse multivariate polynomials over finite fields
