Characterising tree-like Frege proofs for QBF (Q2272983)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Characterising tree-like Frege proofs for QBF |
scientific article |
Statements
Characterising tree-like Frege proofs for QBF (English)
0 references
17 September 2019
0 references
The article is well organized, written, and clear. It combines strategy size with round-base strategy extraction algorithm in order to give a lower bound on any tree-like P+\(\forall\)red proof system, not only that, it is the only way to show such lower bound which does not require showing a lower bound for dag-like P+\(\forall\)red. On page 4, paragraph 1, there is a typo, instead of \(\forall\) reduction must be \(\forall\)-reduction. Finally, on page 4, Definition 5, it would be appropriate, in order to clarify, to give the explicit definition of \textit{range}, not only mention it, because the concept is used in the rest of the article many times.
0 references
proof complexity
0 references
QBF
0 references
Frege systems
0 references
lower bounds
0 references