×
Weispfenning, Volker

The complexity of linear problems in fields. (English) Zbl 0646.03005

J. Symb. Comput. 5, No. 1-2, 3-27 (1988).
Complexity bounds for decision problems) for linear sentences (that means that in atomic subformulas only linear polynomials occur) over different types of fields are established. It is proved that for fields of zero characteristic or for ordered fields (in the latter case inequalities are allowed) these problems can be solved in exponential space and double exponential time. A similar result is obtained for the discretely valued fields. The decision problem for linear sentences with a fixed number of quantifiers can be solved in polynomial time.
Reviewer: D.Yu.Grigor’ev

Cited in 3 Reviews
Cited in 79 Documents

MSC:

03B25 Decidability of theories and sets of sentences
03D15 Complexity of computation (including implicit computational complexity)
12L05 Decidability and field theory
68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity

Keywords:

space and time complexity; ordered fields; Complexity bounds for decision problems; linear sentences
Cite Review PDF
Full Text: DOI

References:

[1] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, ACM Symp. on Computing, 457-464 (1986)
[2] Berman, L., Precise bounds for Presburger arithmetic and the reals with addition (preliminary report), (Proc. 18 IEEE Symp. FOCS (1977)), 95-99
[3] Berman, L., The complexity of logical theories, Theor. Comp. Sci, 11, 71-77 (1980) · Zbl 0475.03017
[4] Brown, S. S., Bounds on transfer principles for algebraically closed and complete, discretely vahted fields, (AMS Memoh’s, 204 (1978)) · Zbl 0383.03022
[5] Collins, G. E., Quantifier elimination for real closed felds, a guide to the literature, (Buehberger, B.; Collins, G. E.; Loos, R., Computer Algebra (1983), Springer: Springer Berlin) · Zbl 0495.03016
[6] Cooper, D. C., Theorem-proving in arithmetic without multiplication, (Meltzer, B.; Michie, D., Machine Intelligence, 7 (1972), Univ. of Edinburgh Press), 91-100 · Zbl 0258.68046
[7] Ferrante, J.; Rackoff, Ch., A decision procedure for the first order theory of real addition with order, SlAM J. Comp, 4, 69-77 (1975) · Zbl 0294.02022
[8] Ferrante, J.; Rackoff, Ch., The computational complexity of logical theories, (Springer, Lee, Notes Math., 718 (1979)) · Zbl 0404.03028
[9] Fischer, M. J.; Rabin, M. O., Super-exponential complexity of Presburger arithmetic, SIAM-AMS Proc, 7, 27-41 (1974) · Zbl 0319.68024
[10] Fürer, M., The complexity of Presburger arithmetic with bounded quantifier alternation depth, Theor. Comp. Sci, 18, 105-111 (1982) · Zbl 0484.03003
[11] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theor. Comp. Sci, 24, 239-277 (1983) · Zbl 0546.03017
[12] Kozen, D., Complexity of Boolean algebras, Theor. Comp. Sci, 10, 221-247 (1980) · Zbl 0428.03036
[13] Macintyre, A.; McKenna, K.; van den Dries, L., Elimination of quantifiers in algebraic structures, Adv. Math, 47, 74-87 (1983) · Zbl 0531.03016
[14] Point, F., Quantifier elimination for projectable L-groups and linear elimination for rings (1983), Thése Mons: Thése Mons Belgium
[15] Prestel, A.; Ziegler, M., Model theoretic methods in the theory of topological fields, J. reine u. ang. Math., 299/300, 318-341 (1978) · Zbl 0367.12014
[16] Reddy, C. R.; Loveland, D. W., Presburger arithmetic with bounded quantifier alternation, (Proc. 10 ACM Symp. Th. of Comp. (1978)), 320-325 · Zbl 1282.68142
[17] van den Dries, L., Quantifier elimination for linear formulas over ordered and valued fields, Bull. Sos. Math. Belg, 33, ser. B, 19-32 (1981) · Zbl 0479.03018
[18] von zur Gathen, J.; Sieveking, M., Weitere zum Erfüllungsproblem polynomial äquivalente kombinatorische Aufgaben, (Specker, E.; Strassen, V., Springer Lec. Notes Comp. Sci.. Springer Lec. Notes Comp. Sci., Komplexität von Entscheidungsproblemen, 43 (1976)) · Zbl 0342.05003
[19] Weispfenning, V., Aspects of quantifier elimination in algebra, (Universal Algebra and its Links. Proc. 25. Arbeitstagung iiber Allgemeine Algebra, Darmstadt, 1103 (1984), Heldermann: Heldermann Berlin) · Zbl 0575.03019
[20] Weispfenning, V., Quantifier elimination and decision procedures for valued fields. Proc. Logic Coll. ’83, Aachen. Part I: Models and sets. (MOiler, G. H., Richter, M. M., eds). Sprhzger Lec. Notes Math, 1103, 419-472 (1985) · Zbl 0584.03022
[21] Weispfenning, V., The complexity of elementary problems in archimedean ordered groups. Proc. EUROCAL ’85 vol. 2, (Caviness, B. F., Springer Lec. Notes Comp. Sci, 204 (1986)), 87-88 · Zbl 0576.06017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.