Proof Complexity
£117.00
Part of Encyclopedia of Mathematics and its Applications
- Author: Jan Krajíček, Charles University, Prague
- Date Published: March 2019
- availability: Available
- format: Hardback
- isbn: 9781108416849
£
117.00
Hardback
Other available formats:
eBook
Looking for an inspection copy?
This title is not currently available on inspection
-
Proof complexity is a rich subject drawing on methods from logic, combinatorics, algebra and computer science. This self-contained book presents the basic concepts, classical results, current state of the art and possible future directions in the field. It stresses a view of proof complexity as a whole entity rather than a collection of various topics held together loosely by a few notions, and it favors more generalizable statements. Lower bounds for lengths of proofs, often regarded as the key issue in proof complexity, are of course covered in detail. However, upper bounds are not neglected: this book also explores the relations between bounded arithmetic theories and proof systems and how they can be used to prove upper bounds on lengths of proofs and simulations among proof systems. It goes on to discuss topics that transcend specific proof systems, allowing for deeper understanding of the fundamental problems of the subject.
Read more- Provides a unified perspective, allowing readers to see the big picture rather than only their specific area
- Covers all the essentials so that newcomers can quickly get up to speed
- Describes how various ideas manifest in different areas of the field, making clear the connections between them
Reviews & endorsements
'… the book has very rich content and its bibliographical material includes all previous books and survey articles related to proof complexity.' Anahit Artashes Chubaryan, MathSciNet
See more reviews'This book is in my view an excellent reference manual for a fundamental topic in mathematical logic and theoretical computer science.' Jaap van Oosten, Boekbesprekingen
Customer reviews
Not yet reviewed
Be the first to review
Review was not posted due to profanity
×Product details
- Date Published: March 2019
- format: Hardback
- isbn: 9781108416849
- length: 530 pages
- dimensions: 241 x 161 x 33 mm
- weight: 0.91kg
- availability: Available
Table of Contents
Introduction
Part I. Basic Concepts:
1. Concepts and problems
2. Frege systems
3. Sequent calculus
4. Quantified propositional calculus
5. Resolution
6. Algebraic and geometric proof systems
7. Further proof systems
Part II. Upper Bounds:
8. Basic example of the correspondence between theories and proof systems
9. Two worlds of bounded arithmetic
10. Up to EF via the <...> translation
11. Examples of upper bounds and p-simulations
12. Beyond EF via the || ... || translation
Part III. Lower Bounds:
13. R and R-like proof systems
14. {LK}_{d + 1/2} and combinatorial restrictions
15. F_d and logical restrictions
16. Algebraic and geometric proof systems
17. Feasible interpolation: a framework
18. Feasible interpolation: applications
Part IV. Beyond Bounds:
19. Hard tautologies
20. Model theory and lower bounds
21. Optimality
22. The nature of proof complexity
Bibliography
Special symbols
Index.
Related Books
related journals
Sorry, this resource is locked
Please register or sign in to request access. If you are having problems accessing these resources please email lecturers@cambridge.org
Register Sign in» Proceed
You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of the print & copy limits on our eBooks.
Continue ×Are you sure you want to delete your account?
This cannot be undone.
Thank you for your feedback which will help us improve our service.
If you requested a response, we will make sure to get back to you shortly.
×