Complexity, Oracles, and Numerical Computation

This chapter is still of a preliminary nature. It contains some basic notions of complexity theory and outlines some well-known algorithms. In addition, less standard concepts and results are described. Among others, we treat oracle algorithms, encoding lengths, and approximation framework in which algorithms are designed and aand computation of numbers, and we analyse the running time of Gaussian elimination and related procedures. The notions introduced in this chapter constitute thenalysed in this book. We intend to stay on a more or less informal level; nevertheless, all notions introduced here can be made completely precise — see for instance Aho, Hopcroft and Ullman (1974), Garey and Johnson (1979).