10

I am asking if there are some good or standard references for proof complexity theory? I didn't find references when I search in internet. Thanks!

Hao Yu
  • 771
  • 4
  • 13

1 Answers1

14

These are three books that I know:

  1. Logical Foundations of Proof Complexity
  2. Bounded Arithmetic, Propositional Logic and Complexity Theory
  3. Logical Foundations of Mathematics and Computational Complexity, Proof complexity chapter

Also, I suggest you read the following papers:

  1. The lengths of proofs
  2. Bounded Arithmetic and Propositional Proof Complexity

==============================================

Update. Jan Krajíček wrote a new book on this topic recently. You can find the final manuscript of it here.