Sentences over Integral Domains and Their Computational Complexities |
| |
Authors: | Shih Ping Tung |
| |
Affiliation: | Department of Mathematics, Chung Yuan Christian University, Chung Li, 32023, Taiwan, Republic of Chinaf1 |
| |
Abstract: | LetRbe a Hilbertian domain and letKbe its fraction field. Letψ(x1, …, xn, y) be a quantifier free arithmetical formula overR. We may also takeψ(x1, …, xn, y) to be an arithmetical formula overKx1, …, xn] and write it asψ(y). In this paper we show that ifRhas enough non-units and x1…xn y ψ(x1, …, xn, y), called an n sentence, is true inR, then y ψ(y) is true inKx1, …, xn]. Also, ifR=KT], whereKis an infinite integral domain andx1…xn y ψ(x1, …, xn, y)is true inR, then y ψ(y) is true inRx1, …, xn]. 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 sentences and diophantine equations with parameters over the ring of integers of a global field are co-NP-complete. 2. The decision problem of sentences over the ring of integers of a global field is NP-complete. 3. LetKbe an infinite domain, the time complexities of the decision problems of equations with parameters and sentences over the polynomial ringKt] are polynomial time reducible to factoring polynomials overK. 4. The decision problem of sentences over all algebraic integer rings is in P. 5. The decision problem of sentences over all integral domains with characteristic 0 is in P. 6. The time complexity of the decision problem of sentences over all integral domains is polynomial time reducible to factoring integers overZand factoring polynomials over finite fields. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|