7 Polynomial-Time Computability 7.1 Feasible Computability Up to now, we have approached computability from the point of view that there should be no constraints either on the time required for a particular computation or on the amount of memory space that might be required. The result is that some total com- putable functions will take a very long time to compute. If a function f grows very rapidly, then for large x, it will take a long time simply to generate the output f (x). But there are also bounded functions that require a large amount of time. In this chapter, 1 we want to adopt a different attitude, and we want to pay some attention to the running time that a program might require. For the most part, we will not attempt to give complete rigorous proofs. Instead, we will concentrate on introducing the concepts and describing the ideas behind the results, and on giving pointers to topics for further study. Of course, the complexity of computing f (x) depends on the program used. Sup- pose we define M(e, x) to be the number of steps the program with G odel number e ¨ uses on input x: