On Some Central Problems in Computational Complexity

In this thesis we examine some of the central problems in the theory of computational complexity, like the trade-offs between time and memory, the power of nondeterminism and parallelism, and the speed gained by adding new operations to random access machines. Our main result is the cahracterization of the power of multiplication in random access acceptors: we show, in Chapter 3, that for such models nondeterministic and deterministic computations are polynomially related and that there is a polynomial relationship between the amount of time required for acceptance by random access machines with multiplication, and the amount of tape required by Turing machines. Thus, the additional power gained by using multiplication is the same as that of memory over time (if any). We derive similar results for some other interesting instruction sets. We also have some results for probabilistic and nondeterministic computations: we define threshold machines and show how probabilistic Turing machines may simulate them, and exhibit a set of complete problems for threshold machines. For nondeterministic computations, we present a hierarchy of the elementary recursive languages obtained by polynomially bounded quantification over objects of higher and higher type, which represent nondeterministic time bounded computations with larger and larger bounds. Finally, we discuss some deterministic computations, and conclude with a look at some open problems