Characterising tree-like Frege proofs for QBF (Q2272983)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Characterising tree-like Frege proofs for QBF |
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
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
0 references
0.8439068794250488
0 references
0.8393893241882324
0 references
0.8369129300117493
0 references
0.8168713450431824
0 references
0.8048038482666016
0 references