ABSTRACT
Efficiency in general describes the extent to which resources such as time, space, energy, and so on are well used for the intended task or purpose. In complexity theory, it is a property of algorithms for solving problems that require at most a number of steps (or memory locations) bounded from above by some polynomial function to be solved. The size of the problem instance is considered in determining the bounding function. Typically, the efficiency of an algorithm could be improved at the cost of solution quality. This often happens when approximate solutions are acceptable. I also interpret efficiency to mean shorter representations of redundant data strings. Essentially, EF measures how far we can get away from the BF in terms of finding quick algorithms for difficult problems studied in complexity theory; see, for example, the work of Levin (1986), Cook (Cook and Reckhow 1979), Karp (1972), and others. It also works toward discovering succinct string encodings, as in the work of Shannon (1948), Kolmogorov (1965), Solomonoff (1960), and Chaitin (Solomonoff 1960). Many fundamental notions related to information and computation could be naturally formalized in terms of their relevance to BF or efficiency.
