Summary: Let \(R\) be a Hilbertian domain and let \(K\) be its fraction field. Let \(\psi(x_1, \dots, x_n,y)\) be a quantifier-free arithmetical formula over \(R\). One may also take \(\psi(x_1, \dots, x_n,y)\) to be an arithmetical formula over \(K[x_1, \dots, x_n]\) and write it as \(\overline\psi (y)\). The authors show that if \(R\) has enough non-units and \(\forall x_1 \dots \forall x_n \exists y \psi(x_1, \dots, x_n,y)\), called an \(\forall^n \exists\) sentence, is true in \(R\), then \(\exists y \overline \psi(y)\) is true in \(K[x_1, \dots, x_n]\). Also, if \(R=K[T]\), where \(K\) is an infinite integral domain and \[ \forall x_1\dots \forall x_n \exists y \psi(x_1, \dots, x_n,y) \] is true in \(R\), then \(\exists y \overline \psi(y)\) is true in \(R[x_1, \dots, x_n]\). These results are applied to find the upper and lower bounds of the time complexities of various decision problems on diophantine equations with parameters and arithmetical sentences.
Some of the results are: 1. The decision problem of \(\forall\exists\) sentences and diophantine equations with parameters over the ring of integers of a global field are co-NP-complete. 2. The decision problem of \(\exists\forall\) sentences over the ring of integers of a global field is NP-complete. 3. Let \(K\) be an infinite domain, the time complexities of the decision problems of equations with parameters and \(\forall \exists\) sentences over the polynomial ring \(K[t]\) are polynomial time reducible to factoring polynomials over \(K\). 4. The decision problem of \(\forall\exists\) sentences over all algebraic integer rings is in P. 5. The decision problem of \(\forall\exists\) sentences over all integral domains with characteristic 0 is in P. 6. The time complexity of the decision problem of \(\forall\exists\) sentences over all integral domains is polynomial time reducible to factoring integers over \(Z\) and factoring polynomials over finite fields.