Time-space and size-space tradeoffs for oblivious computations
David A. Carlson · 1981
A major area of interest in computational complexity is the development of lower bounds on the simultaneous resource requirements of an algorithm implementing a particular problem. Important resources that can be used to determine the cost of computing are an algorithm's execution time, storage space needs, and size. Significant relationships can occur between these parameters, such as tradeoffs, for which it is impossible to achieve two resource values simultaneously. This dissertation investigates the types of tradeoffs which relate the resources of time, space, and size for computations executed in a data-independent manner. We associate a directed acyclic graph with an algorithm, and simulate the allocation of storage space by placing pebbles on vertices of the graph. Using this technique, we are able to demonstrate time-space tradeoffs for a number of data-independent computations. For n-degree polynomial multiplication implemented via Fast Fourier transforms, we show that the product of time and space must grow as (OMEGA)(n('2)log n). Thus, in order to achieve time 0(n(.)log n), a sacrifice in space of (OMEGA)(n) must be made. We develop a graph model for the evaluation of a non-linear recursive function, and exhibit pebbling strategies optimal with respect to either time or space. We also discover that, in certain cases, near optimal time and space can be achieved simultaneously. Another topic which we examine is the consequences of restricting the resource of space too severely. One such consequence is time which grows as superpolynomial in the size of the computation's corresponding graph. We demonstrate that this type of behavior is associated with a particular data-independent sorting algorithm. We also examine the range of space in which superpolynomial time can occur, and show that the lower limit on space can grow as any slowly increasing function of the graph's size. In addition to this, we show that when space is limited, it is impossible to construct graphs of optimal size for the problems of oblivious merging and pattern matching.