000			00550nam a2200193Ia 4500
999			_c14956 _d14956
008			161214s9999 xx 000 0 und d
020			_a9780387950556 _chbk
082			_a004 _bHOM
100			_aHomer, Steven
245		0	_aComputability and Complexity Theory
260			_aNew York: _bSpringer, _c2001
300			_axiii, 194 p.; _bill.: _c24 cm.
490			_aTexts in computer science
520			_aThe theory of computing provides computer science with concepts, models, and formalisms for reasoning about the resources needed to carry out computations and about the efficiency of the computations that use these resources. It provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with other problems. Courses in this subject help students to gain analytic skills and enable them to recognize the limits of computation. For these reasons, a course in theory of computing is usually required in the graduate computer science curriculum. This textbook is intended for use in an introductory graduate course in theoretical computer science. It contains material that should be core knowledge in the theory of computation for all graduate students in computer science. It is self-contained and is best suited for a one semester course. Most of the text can be covered in one semester by moving expeditiously through the core material of Chapters 1 through 5 and then covering parts of Chapter 6. The text starts properly with classical computability theory and builds complexity theory on top of that. Doing so has the pedagogical advantage that students learn a qualitative subject before advancing to a quantitative one. Also, the concepts build from one to the other. For example, although we give a complete proof that the satisfiability problem is NP-complete, it is easy for students to understand that the bounded halting problem is NP -complete, because they already know that classical halting problem is r.e. complete. As a graduate course, students should have some prerequisite preparation. The ideal preparation would be the kind of course that we mentioned above: an undergraduate course that introduced topics such as automata theory, formal languages, computability theory, or complexity theory.
650			_aComputable functions
650			_aautomata theory
650			_acomplexity theory
650			_aNondeterminism
650			_acomputability theory
650			_aComputational complexity
700			_aSelman, Alam L.
942			_2ddc _cBK