The complexity of elementary algebra and geometry

Abstract

The theory of real closed fields can be decided in exponential space or parallel exponential time. In fixed dimension, the theory can be decided in NC. © 1986.