10
$\begingroup$

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!

$\endgroup$
2

1 Answer 1

14
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.