Discussion

We have proposed to regard an abstract function as honestly and effectively implemented if it can be effectively computed given its arguments as constructor terms.

Analogously, we suggest that the cost of generating concrete representations of queries be included in the honestly considered cost of deciding problems regarding abstract objects.

Demanding of an implementation that it also generate its internal representations of the input from an abstract term description of that input precludes the hiding of incomputability in the representation used for concrete implementations and, likewise, obviates cheating on complexity problems by giving away the answer in the representation. It also means that checking parity of a binary string should be considered linear-time (in input length), not constant-time. Put another way, presenting a number with least-significant digit first is just as dishonest as ordering the nodes of a graph by its Hamiltonian path. (In general, the sublinearity of various deterministic algorithms, ignoring the cost of constructing the input, strongly depends on how the input is presented.)

Often, one analyzes alternative representations with respect to the complexity of a set of basic functions. Considering graphs, for example, it is common to compare the adjacency-list representation with adjacency matrices. While the former provides greater efficiency for adding a vertex, it has a steeper edge removal cost. In these cases, the complexity of generating the input representation might be considered another aspect of the complexity tradeoffs.

Many persons who are not conversant with mathematical studies, imagine that because the business of the [Analytical] engine is to give its results in numerical notation, the nature of its processes must consequently be arithmetical and numerical, rather than algebraical and analytical. This is an error. The engine can arrange and combine its numerical quantities exactly as if they were letters or any other general symbols; and in fact it might bring out its results in algebraical notation, were provisions made accordingly. It might develope three sets of results simultaneously, viz. symbolic results; numerical results (its chief and primary object); and algebraical results in literal notation. This latter however has not been deemed a necessary or desirable addition to its powers, partly because the necessary arrangements for effecting it would increase the complexity and extent of the mechanism to a degree that would not be commensurate with the advantages, where the main object of the invention is to translate into numerical language general formulae of analysis already known to us, or whose laws of formation are known to us. But it would be a mistake to suppose that because its results are given in the notation of a more restricted science, its processes are therefore restricted to those of that science. The object of the engine is in fact to give the utmost practical efficiency to the resources of numerical interpretations of the higher science of analysis, while it uses the processes and combinations of this latter.

—Augusta Ada Lovelace, Notes to “On Babbage’s Analytical Engine” (1843)

[emphasis in the original]

 
Source
< Prev   CONTENTS   Source   Next >