The complexity of linear problems in fields (Q1103602): Difference between revisions

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.