Dominance: consistently comparing computational complexity

Though complexity theory strives primarily to categorize problems according to their complexity, it is typically the complexity only of methods of solving problems that we can directly measure. Specifically, we have an upper bound for a problem's complexity: namely, the complexity of the most efficient known solution method for the problem. In order to improve such bounds, it is desired to consider sets of solution methods that are as complete as possible; but, whilst comparisons of computing systems' respective efficiencies can—via O-notation—readily be made when the systems conform to the same computational model and when the comparison is with respect to the same resource, it is not clear how to compare model-heterogeneous sets of solution methods—this imposes a constraint on the size of sets of methods that can be considered, and a corresponding constraint on the quality of bounds on the complexity of problems. Here, we propose the notion of dominance as a way of augmenting the power of O-notation to compare systems' complexity. In particular, our augmentation allows meaningful comparison of the respective complexities, with respect to different resources, of computing systems that conform to different computational models, thus allowing consideration of larger, model-heterogeneous sets of solution methods and, hence, improved bounds on problems' complexity.