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 overK[x1, …, 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 inK[x1, …, xn]. Also, ifR=K[T], whereKis an infinite integral domain and x1… xn y ψ(x1, …, xn, y)is true inR, then y ψ(y) is true inR[x1, …, 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 ![for all for all](http://www.sciencedirect.com/scidirimg/entities/2200.gif) sentences and diophantine equations with parameters over the ring of integers of a global field are co-NP-complete. 2. The decision problem of ![for all for all](http://www.sciencedirect.com/scidirimg/entities/2200.gif) 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 ![for all for all](http://www.sciencedirect.com/scidirimg/entities/2200.gif) sentences over the polynomial ringK[t] are polynomial time reducible to factoring polynomials overK. 4. The decision problem of ![for all for all](http://www.sciencedirect.com/scidirimg/entities/2200.gif) sentences over all algebraic integer rings is in P. 5. The decision problem of ![for all for all](http://www.sciencedirect.com/scidirimg/entities/2200.gif) sentences over all integral domains with characteristic 0 is in P. 6. The time complexity of the decision problem of ![for all for all](http://www.sciencedirect.com/scidirimg/entities/2200.gif) sentences over all integral domains is polynomial time reducible to factoring integers overZand factoring polynomials over finite fields. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|