A first-order formula over a valued field is called linear if it contains n
o products or reciprocals of quantified variables. We give quantifier elimi
nation procedures based on test term ideas for linear formulas in the follo
wing classes of valued fields: discretely valued fields, discretely valued
fields with a z-group as the value group over a language containing predica
tes stating divisibility in the value group, and non-discretely valued fiel
ds. From the existence of the elimination procedures, it follows that the c
orresponding decision problems are ill an alternating single exponential ti
me-space (Berman) complexity class. We exhibit the substructure completenes
s of the considered classes of valued fields w.r.t. linear formulas. (C) 20
00 Academic Press.