Proof complexity

Jan Krajicek


The pdf file contains a complete draft of Parts I, II and III of my forthcoming book "Proof complexity" prepared for the CUP. This is about 85% of the eventual text. There will be one more part (Part IV) that will be available - I plan - in early months of 2018. The Subject, Symbol and Name Indices are not compiled here yet but there are hyperlinks; in particular, these connect references with places where they are cited.

The current draft of the three parts will undertake another round of editing, perhaps substantial at places. I would appreciate a lot any critical comments you may offer. In particular, please point out:

  • any errors, small or big,

  • missing or incorrect bibliographical information,

  • confusing or too brief (or too long) presentation of some topic,

  • topics presently omitted that you think should not be,

  • do not hesitate to point out your own important work that should be treated (I shall keep these suggestions confidential),

  • ...

    Your comments will be most useful if received by May 2018. If you wish, you can use a pdf file with numbered lines to aim your comments at specific places in the draft.

    Thank you!
    J.K., 5.December 2017