Computing Science Group Dominance: Consistently Comparing Computational Complexity

Abstract. 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. Specif-ically, 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 complexi-ties, with respect to different resources, of computing systems that con-form to different computational models, thus allowing consideration of larger, model-heterogeneous sets of solution methods and, hence, im-proved bounds on problems ’ complexity.