Non-deterministic machines are sometimes described as making undetermined ‘choices’ among different possible successor configurations at various points during their computation. But what the foregoing definitions actually describe is a tree \(\mathcal{T}^N_{C_0}\) of all possible computation sequences starting from a given configuration \(C_0\) for a deterministic machine \(N\) (an example is depicted in Figure 1). Given the asymmetry just noted, it will generally be the case that all of the branches in \(\mathcal{T}^N_{C_0(x)}\) must be surveyed in order to determine \(N\)’s decision about the input \(x\).