Although it is not easy, in general, to prove lower bounds on complexity for some problems like sorting, the very basic technique of decision trees succeeds. This paper uses decision trees in order to investigate the complexity of probabilistic, nondeterministic, and alternating modes of computation for problems related to sorting. These probelms are Element Uniqueness, Set Disjointness, Set Membership, Set equality, &egr;-Closeness (including their complements), and a few others, all of which can be specified naturally in the n-dimensional Euclidean space. The technique used for nondeterminism is a slight generalization of both “region counting” by Dobkin/Lipton [1] and “flat counting” by Reingold [2]. While nondeterministic algorithms turn out to be provably more powerful than deterministic ones, this is not the case with probabilistic algorithms. In probabilistic decision trees the proofs employ critical paths. There are n] many such paths for inputs of size n; but in contrast to the deterministic case, the critical paths are not necessarily distinct. However, using a graph-theoretic result it is still possible to prove an n log₂n lower bound on the height of the tree. Finally, some results about alternating decision trees are derived. But here the situation is more difficult and the techniques are not as successful as for the other modes of computation.