Computational complexity of sentences over fields
Hilbert's Irreducibility Theorem is applied to find the upper bounds of the time complexities of various decision problems in arithmetical sentences and the following results are proved: 1. The decision problem of for all there exists sentences over an algebraic number field is in P. 2. The decision problem of for all there exists sentences over the collection of all fields with characteristic 0 is in P. 3. The decision problem of for all there exists sentences over a function field with characteristic p is polynomial time reducible to the factorization of polynomials over Z(p). 4. The decision problem of for all there exists sentences over the collection of all-fields with characteristic p is polynomial time reducible to the factorization of polynomials over Zp. 5. The decision problem of for all there exists sentences over the collection of all fields is polynomial time reducible to the factorization of integers over Z and the factorization of polynomials over finite fields. (c) 2008 Published by Elsevier Inc.
computational complexity fields arithmetical sentences