Logical foundations of proof complexity

Title
  1. Logical foundations of proof complexity / Stephen Cook, Phuong Nguyen.
Published by
  1. Ithaca, NY : Association for Symbolic Logic ; New York, NY : Cambridge University Press, 2010.
Author
  1. Cook, Stephen, 1948-

Items in the library and off-site

Filter by

Displaying 1 item

StatusFormatAccessCall numberItem location
StatusFormatTextAccessUse in libraryCall numberQA267.7 .C695 2010Item locationOff-site

Details

Additional authors
  1. Nguyen, Phuong, 1977-
Description
  1. xv, 479 pages : illustrations; 25 cm.
Summary
  1. "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
  1. Perspectives in logic
Uniform title
  1. Perspectives in logic.
Subject
  1. Computational complexity
  2. Proof theory
  3. Logic, Symbolic and mathematical
  4. Beweis > Mathematische Logik > Komplexität
  5. Mathematische Logik > Beweis (Math.) > Komplexität
  6. Beweis > Komplexität > Mathematische Logik
  7. Komplexität > Beweis (Math.) > Mathematische Logik
  8. Prädikatenlogik
  9. Beweistheorie
  10. Komplexitätstheorie
  11. Symbolisk logik
Contents
  1. 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
  1. Princeton University Library
Bibliography (note)
  1. Includes bibliographical references and index.