Logical foundations of proof complexity
- Title
- Logical foundations of proof complexity / Stephen Cook, Phuong Nguyen.
- Published by
- Ithaca, NY : Association for Symbolic Logic ; New York, NY : Cambridge University Press, 2010.
- Author
Items in the library and off-site
Displaying 1 item
Status | Format | Access | Call number | Item location |
---|---|---|---|---|
Status | FormatText | AccessUse in library | Call numberQA267.7 .C695 2010 | Item locationOff-site |
Details
- Additional authors
- Description
- xv, 479 pages : illustrations; 25 cm.
- Summary
- "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."--Jacket.
- Series statement
- Perspectives in logic
- Uniform title
- Perspectives in logic.
- Subject
- Computational complexity
- Proof theory
- Logic, Symbolic and mathematical
- Beweis > Mathematische Logik > Komplexität
- Mathematische Logik > Beweis (Math.) > Komplexität
- Beweis > Komplexität > Mathematische Logik
- Komplexität > Beweis (Math.) > Mathematische Logik
- Prädikatenlogik
- Beweistheorie
- Komplexitätstheorie
- Symbolisk logik
- Contents
- Machine generated contents note: Ch. I Introduction -- Ch. II Predicate Calculus and the System LK -- Ch. III Peano Arithmetic and Its Subsystems -- Ch. IV Two-Sorted Logic and Complexity Classes -- Ch. V Theory V[superscript 0] and AC[superscript 0] -- Ch. VI Theory V[superscript 1] and Polynomial Time -- Ch. VII Propositional Translations -- Ch. VIII Theories for Polynomial Time and Beyond -- Ch. IX Theories for Small Classes -- Ch. X Proof Systems and the Reflection Principle -- App. A Computation Models.
- Owning institution
- Princeton University Library
- Bibliography (note)
- Includes bibliographical references and index.