A survey of techniques in applied computational complexity

摘要

An attempt is made to introduce the non-expert reader to the many aspects of a relatively new and varied field which seems to be at the same time analysis, algebra and computer science. Computational complexity can be roughly described as the theory of optimizing finite and infinite algorithms for use on digital computers. Even for “simple” problems like the finding of a zero of a real function or even the evaluation of a polynomial, surprisingly deep techniques are necessary. A representative sample of the presently existing bibliography on the subject is included at the end.