A new parameter is introduced to characterize a type of search problem of broad relevance in artificial intelligence, operations research and symbolic logic. This parameter, which we call inter-variable compatibility, is particularly important in that complexity analyses incorporating it are able to capture the dependence of problem complexity on search order used by an algorithm. Thus compatibility-based theories can provide a theoretical basis for the extraction of heuristics for choosing good search orderings—a long-sought goal for such problems, since it can lead to significant savings during search. We carry out expected-complexity analyses for the traditional backtrack algorithm as well as for two more recent algorithms that have been found empirically to be significant improvements: forward checking and word-wise forward checking. We extract compatibility-based ordering-heuristics from the theory for forward checking.