Logical foundations of proof complexity / (Record no. 518266)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02292nam a22003858i 4500 |
| 001 - CONTROL NUMBER | |
| control field | CR9780511676277 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | UkCbUP |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20200124160238.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 | 100212s2010||||enk o ||1 0|eng|d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9780511676277 (ebook) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Cancelled/invalid ISBN | 9780521517294 (hardback) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Cancelled/invalid ISBN | 9781107694118 (paperback) |
| 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 | .C695 2010 |
| 082 00 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 511.3/6 |
| Edition number | 22 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Cook, Stephen, |
| Dates associated with a name | 1948- |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | Logical foundations of proof complexity / |
| Statement of responsibility, etc | Stephen Cook, Phuong Nguyen. |
| 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 | 2010. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 online resource (xv, 479 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 |
| 490 1# - SERIES STATEMENT | |
| სერიის ცნობა | Perspectives in logic |
| 500 ## - GENERAL NOTE | |
| General note | Title from publisher's bibliographic system (viewed on 05 Oct 2015). |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | This book treats bounded arithmetic and propositional proof complexity from the point of view of computational complexity. The first seven chapters include the necessary logical background for the material and are suitable for a graduate course. Associated with each of many complexity classes are both a two-sorted predicate calculus theory, with induction restricted to concepts in the class, and a propositional proof system. The complexity classes range from AC0 for the weakest theory up to the polynomial hierarchy. Each bounded theorem in a theory translates into a family of (quantified) propositional tautologies with polynomial size proofs in the corresponding proof system. The theory proves the soundness of the associated proof system. The result is a uniform treatment of many systems in the literature, including Buss's theories for the polynomial hierarchy and many disparate systems for complexity classes such as AC0, AC0(m), TC0, NC1, L, NL, NC, and P. |
| 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 | Proof theory. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Logic, Symbolic and mathematical. |
| 700 1# - ADDED ENTRY--PERSONAL NAME | |
| Personal name | Nguyen, Phuong, |
| Dates associated with a name | 1977- |
| Relator term | author. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Display text | Print version: |
| International Standard Book Number | 9780521517294 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE | |
| Uniform title | Perspectives in logic. |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | <a href="https://doi.org/10.1017/CBO9780511676277">https://doi.org/10.1017/CBO9780511676277</a> |
No items available.