A survey of space complexity

AbstractThe main properties of deterministic and nondeterministic space complexity classes are given, with emphasis on closure under complementation. Various limitations and generalizations of these classes are studied: weakly space-bounded classes, classes defined by one-way alternating, or probabilistic machines, and nonuniform classes. In each case intrinsic properties of these classes and relationship between these classes are given. Then three ways of relativizing complexity classes are examined. Finally, the space complexity of RAMs is defined and its relation to usual classes is given