Computational complexity : (Record no. 519380)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02735nam a22003378i 4500 |
| 001 - CONTROL NUMBER | |
| control field | CR9780511804106 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | UkCbUP |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20200124160250.0 |
| 006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS--GENERAL INFORMATION | |
| fixed length control field | m|||||o||d|||||||| |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
| fixed length control field | cr|||||||||||| |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 101021s2008||||enk o ||1 0|eng|d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9780511804106 (ebook) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Cancelled/invalid ISBN | 9780521884730 (hardback) |
| 040 ## - CATALOGING SOURCE | |
| Original cataloging agency | UkCbUP |
| Language of cataloging | eng |
| Description conventions | rda |
| Transcribing agency | UkCbUP |
| 050 00 - LIBRARY OF CONGRESS CALL NUMBER | |
| Classification number | QA267.7 |
| Item number | .G65 2008 |
| 082 00 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 511.3/52 |
| Edition number | 22 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Goldreich, Oded, |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | Computational complexity : |
| Remainder of title | a conceptual perspective / |
| Statement of responsibility, etc | Oded Goldreich. |
| 264 #1 - Production, Publication, Distribution, Manufacture, and Copyright Notice (R) | |
| Place of production, publication, distribution, manufacture (R) | Cambridge : |
| Name of producer, publisher, distributor, manufacturer (R) | Cambridge University Press, |
| Date of production, publication, distribution, manufacture, or copyright notice | 2008. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 online resource (xxiv, 606 pages) : |
| Other physical details | digital, PDF file(s). |
| 336 ## - Content Type (R) | |
| Content type term (R) | text |
| Content type code (R) | txt |
| Source (NR) | rdacontent |
| 337 ## - Media Type (R) | |
| Media type term (R) | computer |
| Media type code (R) | c |
| Source (NR) | rdamedia |
| 338 ## - Carrier Type (R) | |
| Carrier type term (R) | online resource |
| Carrier type code (R) | cr |
| Source (NR) | rdacarrier |
| 500 ## - GENERAL NOTE | |
| General note | Title from publisher's bibliographic system (viewed on 05 Oct 2015). |
| 505 0# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Introduction and preliminaries -- P, NP and NP-completeness -- Variations on P and NP -- More resources, more power -- Space complexity -- Randomness and counting -- The bright side of hardness -- Pseudorandom generators -- Probabilistic proof systems -- Relaxing the requirements -- Appendix A: Glossary of complexity classes -- Appendix B: On the quest for lower bounds -- Appendix C: On the foundations of modern cryptography -- Appendix D: Probabilistic preliminaries and advanced topics in randomization -- Appendix E: Explicit constructions -- Appendix F: Some omitted proofs -- Appendix G: Some computational problems. |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Computational complexity. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Turing machines. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Display text | Print version: |
| International Standard Book Number | 9780521884730 |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | <a href="https://doi.org/10.1017/CBO9780511804106">https://doi.org/10.1017/CBO9780511804106</a> |
No items available.