02726nam a2200253Ia 4500999001700000008004100017020002400058082001300082100001800095245004000113260003300153300003500186490003000221520186100251650002502112650002002137650002202157650001902179650002502198650002902223700002002252942001202272952018802284 c14956d14956161214s9999 xx 000 0 und d a9780387950556 chbk a004bHOM aHomer, Steven 0aComputability and Complexity Theory aNew York: bSpringer, c2001 axiii, 194 p.; bill.: c24 cm. aTexts in computer science 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. aComputable functions aautomata theory acomplexity theory aNondeterminism acomputability theory aComputational complexity aSelman, Alam L. 2ddccBK 00102ddc406004_000000000000000_HOM70918512aDAIICTbDAIICTd2010-02-19eHimanshu Book Co.; Invoice No# 101481; 2009-12-20g5508.83l1o004 HOMp024134r2019-12-09s2019-12-06yBK