Editing Alternating Turing machine (section)

=== Resource bounds ===

When deciding if a configuration of an ATM is accepting or rejecting using the above definition, it is not always necessary to examine all configurations reachable from the current configuration.  In particular, an existential configuration can be labelled as accepting if any successor configuration is found to be accepting, and a universal configuration can be labelled as rejecting if any successor configuration is found to be rejecting.

An ATM decides a [[formal language]] in time <math>t(n)</math> if, on any input of length {{mvar|n}}, examining configurations only up to <math>t(n)</math> steps is sufficient to label the initial configuration as accepting or rejecting.  An ATM decides a language in space <math>s(n)</math> if examining configurations that do not modify tape cells beyond the <math>s(n)</math> cell from the left is sufficient.

A language that is decided by some ATM in time <math>c\cdot t(n)</math> for some constant <math>c>0</math> is said to be in the class <math>\mathsf{ATIME}(t(n))</math>, and a language decided in space <math>c\cdot s(n)</math> is said to be in the class <math>\mathsf{ASPACE}(s(n))</math>.