Skip to content
Register Sign in Wishlist

Proof Complexity


Part of Encyclopedia of Mathematics and its Applications

  • Date Published: March 2019
  • availability: Available
  • format: Hardback
  • isbn: 9781108416849

£ 105.00

Add to cart Add to wishlist

Other available formats:

Looking for an inspection copy?

This title is not currently available on inspection

Product filter button
About the Authors
  • 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.

    • 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
    Read more

    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

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity


    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?


    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

    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
    Special symbols

  • Author

    Jan Krajíček, Charles University, Prague
    Jan Krajíček is Professor of Mathematical Logic in the Faculty of Mathematics and Physics at Charles University, Prague. He is a member of the Academia Europaea and of the Learned Society of the Czech Republic. He has been an invited speaker at the European Congress of Mathematicians and at the International Congresses of Logic, Methodology and Philosophy of Science.

Sign In

Please sign in to access your account


Not already registered? Create an account now. ×

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner Please see the permission section of the catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

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.

Please fill in the required fields in your feedback submission.