A natural outgrowth of the study of unrestricted computations is the examination of resource-bounded computations. This chapter aims at such a study, and in many cases it turns out to be simply a refinement of the study conducted in Chapter 4.
The first section of this chapter introduces the models of random access machines as abstractions for computers. It also introduces the notions of time and space for random access machines and Turing transducers, and relates the resource requirements of these different models. The second section shows the existence of a hierarchy of problems; as established by the time required for their solutions. In addition, Section 2 argues about the feasibility of "polynomial time" computations, the infeasibility of "exponential time" computations, and the importance of the "easiest" hard problems. The third and fourth sections consider the place of "nondeterministic polynomial" time in the hierarchy, and propose some "easiest" hard problems. The fifth section considers space-bounded computations. And the sixth section deals with the hardest problems among those problems that can be solved in polynomial time.
5.1 Time and Space
5.2 A Time Hierarchy
5.3 Nondeterministic Polynomial Time
5.4 More NP-Complete Problems
5.5 Polynomial Space
5.6 P-Complete Problems
Exercises
Bibliographic Notes