ABSTRACT
Complexity theory is a device for measuring how complicated a problem is (from a computational point of view), or how much computer time it will take to solve it. As this book has made clear, computation (and the theory of computation) looms large in modern mathematical science. Of particular interest is the question of which problems can be solved in a
reasonable amount of time, and which will require an inordinate or impractical amount of time. Problems of the latter sort are termed computationally expensive. Problems of the former type are called feasible. Just as an instance, the problem of factoring a whole number with 200 digits is computationally expensive. This could actually take many years, even on a fast digital computer. But if instead I say to you
Here is a 200-digit number N . I claim that these two 100digit numbers p and q are its prime factors. Please verify this assertion.
