Characterising tree-like Frege proofs for QBF (Q2272983)

From MaRDI portal





scientific article; zbMATH DE number 7106204
Language Label Description Also known as
default for all languages
No label defined
    English
    Characterising tree-like Frege proofs for QBF
    scientific article; zbMATH DE number 7106204

      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