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!
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Previously posted on math.SE (with no answers): Reference for proof complexity theory. $\endgroup$– Martin SleziakCommented Sep 10, 2017 at 15:42
-
$\begingroup$ Perhap you could expand on what you mean by "proof complexity theory"? In the meantime, maybe this earlier MO question is relevant: Deep theorems and long proofs. In particular, see Joel Hamkins' references there. $\endgroup$– Joseph O'RourkeCommented Sep 10, 2017 at 15:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
These are three books that I know:
- Logical Foundations of Proof Complexity
- Bounded Arithmetic, Propositional Logic and Complexity Theory
- Logical Foundations of Mathematics and Computational Complexity, Proof complexity chapter
Also, I suggest you read the following papers:
==============================================
Update. Jan Krajíček wrote a new book on this topic recently. You can find the final manuscript of it here.
answered Sep 10, 2017 at 15:58