 # Honest Complexity

We turn now to the question of complexity of problems over abstract domains. But before one can measure complexity, one needs a measure of input size and a measure of the cost of a computation as a function of that size.

A size measure is associated with each (ground) term over the generators. This provides the flexibility of considering each of the various views of the same abstract element differently. Since problems often involve more than one input value, we need to measure the size of tuples of terms.

Definition 6.10 (Size) A size measure for an abstract domain is a function |-|: H* ^ N, where H* is the set of tuples of (ground) terms over the generators of the domain.

Complexity is measured with respect to this size, whatever it may be.

Examples of size measures for terms denoting graphs are tree height of the term, as well as the number of vertices or number of edges in a graph. Note that the two latter measures assign the same size to all terms of the same graph. Usually the size of a tuple is the sum of the sizes of its individual components.

One might argue that a size measure should not be this arbitrary, but should enforce a compact representation of the abstract elements, as Garey and Johnson demanded of the representation of numbers in the paragraphs quoted at the outset, namely, that the size of a natural number n should be order log n. In many cases, however, this is too demanding. For instance, a set of n elements taken from some unordered set may have n! reasonable representations. Checking equality between two such representations, in order to choose a single canonical representation for each set, might require a quadratic number of element comparisons. Even more involved is the case of graphs. If we are asked to decide the existence of a Hamiltonian path in an unlabeled graph, we should not demand that there be a unique or almost-unique way of constructing each graph, considering that graph isomorphism is a difficult problem. But there are exponentially many isomorphic graphs, so the standard representations of graphs are as wasteful as is the unary encoding of numbers. It is also standard practice to store data in compressed form, and it can easily take exponential time and space to reconstruct before manipulating.

The cost assigned to a computation over the concrete domain C depends on the relevant aspects of the computational model in question. For example, the cost can be the number of steps of a RAM model or the number of tape cells used by a Turing machine. (RAMs are in fact nearly optimal for time and space .) As with the size measure, cost is also in “the eyes of the beholder”. Given a cost measure for computation in the model, we define the cost of terms, as follows:

Definition 6.11 (Cost) The cost к (h (t1,.tt)) of a concrete term h(t1,.. .,h) is the cost of a computation that constructs the concrete values Ci e C arguments ti and then computes h(c1,..., q), the value of h for the concrete values thus obtained.

In some cases the cost of a computation might be the sum of the costs of its steps, as is natural for time complexity, while in other cases a different aggregation, such as maximum, is appropriate, as is done for space complexity. Often, the declared size of the input is approximately the cost of constructing it, so the impact on complexity of including the cost of construction is negligible.

Equipped with size and cost measures, we are ready to formalize our intuition of when a complexity measure is honest. The complexity of an implementation must take the specific means of representation into account. We have demanded that an honest implementation of an abstract function also provide implementations of the abstract domain’s equality and generators (Definition 6.4). We may assume that every generator has a unique implementation. (Different implementations should have different names, thus refer to different, but possibly equivalent, generators.)

Our definition of the complexity of a function resembles the standard one; it is just that our notion of the cost of computing a function includes the cost of generating the representation of the input.

Definition 6.12 (Honest Complexity) Consider an abstract domain A with ground generator terms H and an honest implementation h : C1 ^ C over concrete domain C, implementing a function h : A1 ^ A over A. Let m : N ^ N be a complexity measure. Then we say that h has honest (worst-case) complexity of at most m if к(h(t)) < m(|tj), for all tuples t e H of terms.

Average and probabilistic complexities can be defined analogously.

While the complexity of implementing generators influences the complexity of implementing f, the complexity of implementing the equality relation need not affect it. For example with abstract graphs, equality checks are very involved, yet many graph operations need not check for graph equality (isomorphism). We do insist, however, that every implementation also implements the equality check in order to enforce a correct interpretation of the abstract domain—having the ability to use the equality implementation, Abe, the person posing instances of the function f, can verify whether the result of f’s implementation is indeed proper. (Cf. Sect. 6.5 and the proof of Theorem 6.1.)

To sum up, to preclude dishonest measures of complexity, we require that the implementor Cay charge not only for calculating the answer to Abe’s query, but also for building its native representation of the query from Abe’s language of generators. That way, any new information hidden in the representation is put there by Cay and the costs incurred are charged for.