Stephen Cook, Phuong Nguyen

Logical Foundations of Proof Complexity

• Broschiertes Buch

Produktbeschreibung

A treatise on bounded arithmetic and propositional proof complexity by the leader in the field.

Produktdetails

• Verlag: Cambridge University Press
• Seitenzahl: 496
• Erscheinungstermin: 23. Dezember 2013
• Englisch
• Abmessung: 234mm x 156mm x 29mm
• Gewicht: 837g
• ISBN-13: 9781107694118
• ISBN-10: 1107694116
• Artikelnr.: 40550859

Autorenporträt

Stephen Cook is a journalist and author with extensive experience in national newspapers and magazines, including 18 years at The Guardian. He has published five novels and two non-fiction books.

Inhaltsangabe

1. Introduction
2. The predicate calculus and the system
3. Peano arithmetic and its subsystems
4. Two-sorted logic and complexity classes
5. The theory V0 and AC0
6. The theory V1 and polynomial time
7. Propositional translations
8. Theories for polynomial time and beyond
9. Theories for small classes
10. Proof systems and the reflection principle
11. Computation models.