Parallel Real-time Complexity Theory

by Stefan D. Bruda, PhD thesis, Department of Computing and Information Science, Queen's University at Kingston, April 2002. Complete manuscript (930 K characters).

Abstract: We present a new complexity theoretic approach to real-time computations. We define timed omega-languages as a new formal model for such computations, that we believe to allow a unified treatment of all variants of real-time computations that are meaningful in practice. To our knowledge, such a practically meaningful formal definition does not exist at this time.

In order to support our claim that timed omega-languages capture all the real-time characteristics that are important in practice, we use this formalism to model the two most important features of real-time algorithms, namely the presence of deadlines and the real-time arrival of input data. We emphasize the expressive power of our model by using it to formalize aspects from the areas of real-time database systems and ad hoc networks.

We also offer a complexity theoretic characterization of parallel real-time computations. First, we define complexity classes that capture the intuitive notion of resource requirements for real-time computations in a parallel environment. Then, we show that real-time algorithms form an infinite hierarchy with respect to the number of processors used, and that all the problems solvable in nondeterministic logarithmic space (NLOGSPACE) can be solved in real time by a parallel machine, no matter how tight the real-time constraints are. As well, we show that, once real-time constraints are dropped, several other real-time problems are in effect in NLOGSPACE. Therefore, we conjecture that NLOGSPACE contains exactly all the computations that admit feasible (poly(n) processors) real-time parallel implementations.

In the context of these results, the issue of real-time optimization problems is investigated. We identify the class of such problems that are solvable in real time, and we show that, for a large class of optimization problems, a parallel algorithm can report in real time a solution that is arbitrarily better than the solution reported by a sequential algorithm.

We also address the problem of real-time approximation algorithms. We identify problems that do not admit good approximation solutions in real time. We also show that bin packing admits a good real-time approximation algorithm.