On the Problem of Finding Natural Computational Complexity Measures

Abstract

To develop an abstract theory which deals with the quantitative aspects of computing we need a deeper understanding of how to define "natural" computational complexity measures axiomatically. To this end, this paper summarizess the principal properties which hold for some natural complexity measures but not for all measures and which have been proposed as desirable properties of natural measuress. The paper discusses the nature of these properties, studies their interrelations and their possible values towards defining natural computational complexity measures. A number off open problems are discussed and directions for further research are suggested.