| 000 -LEADER |
|---|
| fixed length control field |
00550nam a2200193Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION |
|---|
| fixed length control field |
161214s9999 xx 000 0 und d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
9780387950556 |
| Terms of availability |
hbk |
| 082 ## - DEWEY DECIMAL CLASSIFICATION NUMBER |
|---|
| Classification number |
004 |
| Item number |
HOM |
| 100 ## - MAIN ENTRY--PERSONAL NAME |
|---|
| Personal name |
Homer, Steven |
| 245 #0 - TITLE STATEMENT |
|---|
| Title |
Computability and Complexity Theory |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) |
|---|
| Place of publication, distribution, etc |
New York: |
| Name of publisher, distributor, etc |
Springer, |
| Date of publication, distribution, etc |
2001 |
| 300 ## - PHYSICAL DESCRIPTION |
|---|
| Extent |
xiii, 194 p.; |
| Other physical details |
ill.: |
| Dimensions |
24 cm. |
| 490 ## - SERIES STATEMENT |
|---|
| Series statement |
Texts in computer science |
| 520 ## - SUMMARY, ETC. |
|---|
| Summary, etc |
The 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 ## - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name as entry element |
Computable functions |
|
|---|
| Topical term or geographic name as entry element |
automata theory |
|
|---|
| Topical term or geographic name as entry element |
complexity theory |
|
|---|
| Topical term or geographic name as entry element |
Nondeterminism |
|
|---|
| Topical term or geographic name as entry element |
computability theory |
|
|---|
| Topical term or geographic name as entry element |
Computational complexity |
| 700 ## - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Selman, Alam L. |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) |
|---|
| Source of classification or shelving scheme |
|
| Item type |
Books |