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
    0 references
    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

    Identifiers