Computational Complexity on Register Machines

Abstract

This thesis investigates the computational complexity of programs based on their running time. A program consists of an arbitrary flowchart defined over some instruction set of assignments and test instructions, and computes a unique function. Each instruction set specifies an order code for a particular register machine, whose registers A_1, A_2, ... can contain arbitrary integers. Each instruction set includes the basic set I_0: assignments A_j:=A_k+1, A_j:=A_k, A_j:=A_k-1, A_j:=0; tests A_j=0, A_j>=0. It is shown that programs defined over just I_0 can be speeded up by an arbitrary linear factor. A formal demonstration of this result uses a new technique for verifying the correctness of equivalence preserving transformations. It is shown that this speed up property fails to hold if I_0 is augmented with the assignments A_i:=A_j+A_k, A_i:=A_j-A_k. It is shown that the problem of determining whether or not a given function can be computed within a certain time bound can be reduced to the problem of showing whether or not a different function can be computed in real time. Finally, criteria are established for showing that, under certain conditions, a function is not real time computable.