Proof complexity generators

Jan Krajicek




The current version of a complete draft of my "Proof complexity generators" (a short monograph in preparation):

  • version - v6 (May 2024, this is likely the last intermediate version before the final one).

    Main changes:
    - v2 vs. v1: Sec.6.5 removed (to be revised)
    - v3a vs. v2: revised Sec.6.5 is back
    - v4 vs. v3a: new Sec.8.5
    - v5a vs. v4: substantial editing (new or reformulated statements), primarily in Secs. 2.1, 4.2, 6.5, 8.2, 8.4 (formerly 8.7) and 10.2
    - v6 vs. v5a: some editing, primarily in Secs. 2.1, 8.4 and 10.2




    I will appreciate comments (general or specific) on any aspect of this work. In particular, please point out missing (or incorrect) references to a relevant literature (do not hesitate to point out your own work).

    The comments will be most helpful if received before summer 2024. Thank you.