## Complexity

Mere computability investigates the algorithmic solvability of (decision or function) problems in principle. Although this is often already difficult enough to establish (and for many natural problems even wrong), in practice one usually wants efficient a solution: by devising data structures and algorithms and analyzing their worst-case behavior. Here, exponential asymptotic growth is generally considered inefficient -- yet a refined diagonalization argument (the hierarchy theorem due to Hartmanis and Stearns) proves that some decidable problems may require such running times for their solution. This raises the question of optimality of an algorithm, that is, how close it comes asymptotically to the intrinsic difficulty of the problem it solves. Put differently: is it worth while to try improving it or not?

To avoid possible confusion with heuristics: We consider here as algorithm only one formally correct with an asymptotic running time bound provably obeyed on every possible input.

This 'intrinsic difficulty' of a problem is called its complexity; and the running time of any algorithm solving it constitutes (asymptotically) an upper bound. Conversely, if this can be complemented by a matching lower bound, it means that the algorithm is optimal.

Such a lower bound asserts that any conceivable algorithm solving the problem requires asymptotically a certain number of steps. Thus taking into account all possible (even prospective) algorithms is, understandably, usually quite challenging. Moreover for such a claim referring to all algorithms to make sense, the underlying model of computation needs to be specified rather precisely.

Some minor details of its definition often become irrelevant when focussing on asymptotic growth, though. Moreover switching to an asymptotically superior algorithm beats, for sufficiently large inputs, any constant factor performance improvement gained by, e.g., purchasing faster hardware.

As indicated above, time (i.e. the number of steps) is often the primary criterion for efficiency. However 'fast' algorithms in this sense may turn out impractical because they would exceed other limited ressources such as space (i.e. memory consumption), communication, or #processors in parallel computing.