Computability and Complexity Theory (Record no. 106266)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 04093nam a22005055i 4500 |
| 001 - CONTROL NUMBER | |
| control field | 978-1-4614-0682-2 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | DE-He213 |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20140220083733.0 |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
| fixed length control field | cr nn 008mamaa |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 111209s2011 xxu| s |||| 0|eng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9781461406822 |
| -- | 978-1-4614-0682-2 |
| 024 7# - OTHER STANDARD IDENTIFIER | |
| Standard number or code | 10.1007/978-1-4614-0682-2 |
| Source of number or code | doi |
| 050 #4 - LIBRARY OF CONGRESS CALL NUMBER | |
| Classification number | QA75.5-76.95 |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | UY |
| Source | bicssc |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | UYA |
| Source | bicssc |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | COM014000 |
| Source | bisacsh |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | COM031000 |
| Source | bisacsh |
| 082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 004.0151 |
| Edition number | 23 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Homer, Steven. |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | Computability and Complexity Theory |
| Medium | [electronic resource] / |
| Statement of responsibility, etc | by Steven Homer, Alan L. Selman. |
| 250 ## - EDITION STATEMENT | |
| Edition statement | 2. |
| 264 #1 - | |
| -- | Boston, MA : |
| -- | Springer US : |
| -- | Imprint: Springer, |
| -- | 2011. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | XVI, 298p. 50 illus. |
| Other physical details | online resource. |
| 336 ## - | |
| -- | text |
| -- | txt |
| -- | rdacontent |
| 337 ## - | |
| -- | computer |
| -- | c |
| -- | rdamedia |
| 338 ## - | |
| -- | online resource |
| -- | cr |
| -- | rdacarrier |
| 347 ## - | |
| -- | text file |
| -- | |
| -- | rda |
| 490 1# - SERIES STATEMENT | |
| Series statement | Texts in Computer Science, |
| International Standard Serial Number | 1868-0941 |
| 505 0# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Preliminaries -- Introduction to Computability -- Undecidability -- Introduction to Complexity Theory -- Basic Results of Complexity Theory -- Nondeterminism and NP-Completeness -- Relative Computability -- Nonuniform Complexity -- Parallelism -- Probabilistic Complexity Classes -- Introduction to Counting Classes -- Interactive Proof Systems -- References -- Author Index -- Subject Index. |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations. Subsequent chapters move from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability focus on the limitations of computability and the distinctions between feasible and intractable. Substantial new content in this edition includes: a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of Karp─Lipton. a chapter studying properties of the fundamental probabilistic complexity classes a study of the alternating Turing machine and uniform circuit classes. an introduction of counting classes, proving the famous results of Valiant and Vazirani and of Toda a thorough treatment of the proof that IP is identical to PSPACE With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential and practical learning tool. Topics and features: Concise, focused materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes Contains information that otherwise exists only in research literature and presents it in a unified, simplified manner Provides key mathematical background information, including sections on logic and number theory and algebra Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Computer science. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Information theory. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Computer software. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Computer Science. |
| 650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Theory of Computation. |
| 650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Algorithm Analysis and Problem Complexity. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Selman, Alan L. |
| Relator term | author. |
| 710 2# - ADDED ENTRY--CORPORATE NAME | |
| Corporate name or jurisdiction name as entry element | SpringerLink (Online service) |
| 773 0# - HOST ITEM ENTRY | |
| Title | Springer eBooks |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Display text | Printed edition: |
| International Standard Book Number | 9781461406815 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE | |
| Uniform title | Texts in Computer Science, |
| -- | 1868-0941 |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://dx.doi.org/10.1007/978-1-4614-0682-2 |
| 912 ## - | |
| -- | ZDB-2-SCS |
No items available.